偽コインのパズル

http://d.hatena.ne.jp/nishiohirokazu/touch/20120111/1326272867 2011

ソフトウェアエンジニアによる「エンジニアは能力によって10倍以上の生産性の差がある」って主張、エンジニア以外からは「ハッタリかましすぎ、そんなわけあるかアホ」と思われてると思うので偽コイン探しのパズルの話をすると良いと思う

• Q1: 80枚のコインがある、1枚だけ少し重い偽コインが混じっている。天秤を使ってそれを見つけたい。
• A1: 素朴なやり方
  • 天秤の片方の皿にコインを1枚乗せ、もう片方の皿にコインを1枚ずつ乗せて、どちらかの皿が下がったらその皿の上のコインが偽物
  • 1～79回の比較で偽コインが見つかる。
• A2: もう少しマシな方法
  • コインを2枚ずつ取り、それを天秤の左右に載せる
  • 1～40回の比較で偽コインが見つかる
• A3: 少し頭のよい方法
  • 80枚のコインを40枚ずつに分けて天秤の左右に載せる。下がった側の40枚に偽コインが含まれていることがわかる。
  • 40枚のコインを20枚ずつに分けて天秤の左右に載せる。下がった側の20枚に偽コインが含まれていることがわかる。
  • 20枚のコインを10枚ずつに分けて天秤の左右に載せる。下がった側の10枚に偽コインが含まれていることがわかる。
  • 10枚のコインを5枚ずつに分けて天秤の左右に載せる。下がった側の5枚に偽コインが含まれていることがわかる。
  • 5は奇数なので1枚足して、3枚ずつに分けて天秤の左右に載せる。下がった側の3枚に偽コインが含まれていることがわかる。
  • 3は奇数なので1枚足して、2枚ずつに分けて天秤の左右に載せる。下がった側の2枚に偽コインが含まれていることがわかる。
  • 2枚のコインを1枚ずつ天秤の左右に載せる。下がった方のコインが偽コイン。
  • 7回の比較で偽コインが見つかる。
  • これは二分探索と呼ばれる方法、アルゴリズムの勉強をしたエンジニアなら誰でも知っている
• A4: もっと頭のよい方法
  • 80枚のコインを27,27,26に三分割して、27枚ずつ左右に載せる。
    • 傾いたら下がった方に偽コインがある。傾かなければ載せなかった26枚に偽コインがある。
  • 27枚のコインを9枚ずつに三等分して、9枚ずつ左右に載せる。
  • 9枚のコインを3枚ずつに三等分して分けて、左右に載せる。
  • 3枚のコインを三等分して、1枚ずつ左右に載せる。
  • 4階の比較で偽コインが見つかる。
• このように、やり方の良しあしによって偽コインを見つけるまでの作業量は10倍以上変わる。

Q2: 80枚のコインがある、1枚だけ少し重さの違う偽コインが混じっている。天秤を使ってそれを見つけたい。

• Q1とは問題条件が変わったことに気づく必要がある。
• Q1を解くのに使った「3分割する」という手法が使えないことに気付く必要がある。
  • 3分割して左右に載せて皿が下がったとしても、偽コインが重いのか軽いのか不明なので、どちらの皿に偽コインがあるのかわからないから。
• ならばどうするか
  • これを自分の頭で考え着く力が求められる。
• この場合、天秤が傾けば右か左かのどちらかに偽コインがあることがわかるのだから、80枚のコインを20,20,40に分けて、20枚ずつを左右の皿に載せればよい。傾くか傾かないかで偽コインの所在を40枚のコインに絞り込むことができる。
  • つまり、少し変形することでA3の方法に帰着することができる

Q3: 80枚のコインがある、2枚、少し重い偽コインが混じっている。偽コイン同士の重さは同じとする。天秤を使ってどうやってみつけるか。

• 探し物が複数になると難易度が跳ね上がる。
• 40枚ずつ天秤の左右に載せて、
  • ケース1: 傾いた場合は、その40枚の中に2枚の偽コインがある
  • ケース2： 傾かなかった場合は左右両方の40枚にそれぞれ1枚ずつ偽コインがある。
  • ケース1の場合は、同様に半分ずつ天秤の左右に載せることを行う。
  • ケース2の場合には偽コインが1枚なのでA4の方法に帰着できる。

Q4: 80枚のコインがある、少し重い偽コインが1枚以上混じっている。偽コイン同士の重さは同じとする。天秤を使ってどうやってみつけるか。

• 探すべきものの個数が不明であることで、難易度がさらに上がっている。
• ちょっと僕も、この場合の最適な方法が何かはすぐにはわからない。
• 問題が複雑すぎる時には、まず小さい問題を考える。
  • コインが2枚で、うち何枚が偽コインかわからない場合、1枚ずつ天秤に載せる。
  • 傾いた場合、下がった方が偽コイン。
  • 傾かない場合、両方偽コインまたは両方本物コイン。
  • 「2枚のうち1枚以上偽コイン」の条件があれば「両方偽コイン」に決まるが、80枚のうちの2枚だったらその条件は期待できない。
  • 傾いた場合、本物コイン1枚、偽物コイン1枚、偽物を0枚以上含むコインが78枚
  • 傾かない場合、本物または偽物の2枚ペア1組、偽物を0枚以上含むコインが78枚
• 最適解とは言えないがとりあえず一つの解
  • 80枚を2枚ずつの40組に分けて、1枚ずつ天秤に載せる。
  • 高い確率で、本物偽物に分かれる組が1組以上ある(なかった場合は後で検討)
    • わかれなかった組の片方を本物コインと比較することでそのペアが本物か偽物かがわかる
    • 40回の比較の後、最悪39回の比較で全部特定できる。
  • 全部ペアになってしまった場合
    • そのペア20組に分けて、1ペアずつ天秤に載せる
    • 傾けば重い側が偽物ペアとわかる。
    • 高い確率で、本物偽物ペアに分かれる組が1組以上ある(なかった場合は後で検討)
      • 前回と同様に比較することで別れなかったペアが本物か偽物かが特定できる
      • 40回の比較の後、20回の比較をして、その後最悪19回の比較で全部特定できる
    • わかれなかった場合
      • 8枚ずつ10組に分けて、2ペア(4枚)ずつ天秤に載せる
      • 1組以上が分かれた場合は前回同様
      • わかれなかった場合は16枚ずつの5組
      • それでも別れなければ32枚、32枚、16枚、に分けて32枚同士を比較
      • それでもわかれなければ64枚と16枚の「すべて本物かすべて偽物」と、不明の16枚が残るので、64枚のうちの16枚を不明の16枚と比較。
      • 下がった側が偽物。
      • 釣り合うなら「すべて偽物」に確定。(1枚以上偽物がある条件から「すべて本物」があり得ないため)
      • このケースでの比較回数は40+20+10+5+1+1で77回
        • というわけで手順は複雑だけどもどの経路でも最悪79回の比較で偽コインが見つかる
• もう少し頭良さそうな解
  • 80枚を2枚ずつの40組に分けて、1枚ずつ天秤に載せる。
  • 傾くペアXが発見された時点で、以降の天秤では2枚ずつ比較することができる
    • Xより重いなら両方偽コイン、軽いなら両方本物コイン、釣り合うなら1枚ずつ、ということがわかる
    • 前記の方法では「1回比較して釣り合って、その片方に対してもう一度比較」という2回の比較をしなければ「両方偽コイン」「両方本物コイン」のケースは確定しなかったが、このやり方なら1回の比較で確定する。
    • 代わりに「偽物本物1枚ずつ」のケースは、1回で確定していたのが2回必要になる。
    • 偽物の存在確率pがいくらであっても、「両方偽物または両方本物」の確率$p^2+(1-p{)}^2$は「偽物本物1枚ずつ」の確率$2p(1-p)$ 以上なので、確率的にこちらの方が回数が減る
    • $p^2+(1-p{)}^2-2p(1-p)=(p-(1-p){)}^2=(2p-1{)}^2\ge 0$
    • 最悪ケースの回数は変わらないと思うが…
    • 期待値の議論をするなら入力の分布で何が等確率なのか議論すべきだな…

Q5: 80枚のコインがある、少し重さの違う偽コインが1枚以上混じっている。偽コイン同士の重さは同じとする。天秤を使ってどうやってみつけるか。

• この出題を見た時には「問題条件が不足していて解くことができない」と気付くことが必要。
• 重い偽コインが40枚ある場合は軽い方が本物で、軽い偽コインが40枚ある場合は重い方が本物だが、このどちらが正解であるかを天秤で識別することはできない。
• 問題条件に「本物コインの方が偽物コインより枚数が多い」などの条件が付いていないと解けない。