考察(2)

可能性を等分しろ

12枚のコインに対する第一回の比較として「AとBを比べる」と するのはどうだろうか。すぐわかるようにこれは不適当だ。 天秤が傾いたときはラッキーだ。次の比較で結論を出すことができる。 しかしつりあってしまったら残り2回の比較で確実に偽物をみつける ことはもうできない。

なぜ「できない」といいきれるのか。 天秤による比較はグループを最大で3分割できる。2回使うなら9分割だ。 しかし可能性はまだ20も残っていて、9のグループにひとつずつ入れることは 不可能だ。だからできないといいきれる。

「12枚の場合は3回で判定できる」というのは、最悪の場合にも 天秤を3回しか使わないという意味だ。最悪の場合に7回使って しまうのならそれは「7回で判定する手順」でしかない。つまり 「失敗したときの損がばかにならない」。したがって最良の手順では 比較の方針は最悪の場合に最良であるはずだ。言いかえれば どの回の比較も残っている可能性を等分しようとするものでなくてはならない。

12枚のコインには最初24個の可能性がある。第一回の比較では それらを8個ずつに等分するのがベストだということになる。はじめに紹介した手順は そのとおりのことをしている。

お助けコイン

コインが4枚の場合を考えてみてほしい。

可能性は8個しかない。天秤を2回使えば可能性を9分割できるから2回で 判定できるように思える。しかしこれは無理で、どうしても3回使う必要がある。 その原因は、両方の皿に同じ枚数のコインを置かないと比較が できないという天秤の性質だ。8個の可能性は(3,3,2)に分けるのが ベストなのに、天秤の性質によって(2,2,4)または(4,4,0)にしか分けることが できないのだ。可能性が4個入っているグループがある以上、あと1回の比較で 確実に偽物を判定することはもうできない。結局4枚のコインは天秤を3回 使うことになる。

「あれっおかしいな」と思う人がいるかもしれない。 コインが12枚で第一回の比較が水平だったとき、残る可能性は次のように なったのを覚えているだろうか。

この状態は「コインが4枚のときの問題」と同じにみえる。 しかしこのあと2回で判定できてしまうのだ。なぜか。

それは「お助けコイン」が使えるからだ。4枚のコインに、 本物だとわかっているコインを一枚追加して5枚にしてみよう。 すると2回で判定できるようになるのである。

「お助けコイン」を使うことで、両方の皿に同じ枚数のコインを 置かなければならないという制約から逃れることができ、 可能性をうまく(3,3,2)に分けた比較ができるようになるのである。

「お助けコイン」は本物だとわかっているコインでなくてはならない。 最初はどのコインも本物かどうかわからないから第一回の比較には使えない。 第二回以降の比較ではいつでも使える。必要なだけのお助けコインが必ず あることはアルゴリズムのところで証明する。