「可能性の分割」に着目してアルゴリズムに到達するまでの話。
何枚かのコインの中に、1枚だけ偽物がまぎれこんだ。 偽物は本物とは微妙に重さが違うという。両天秤を使って 「どれが偽物で、それは本物より重いのか軽いのか」を 判定したいが、そのとき天秤を使う回数をできるだけ少なくしたい。 なお天秤にはコインしか乗せることができないものとする。分銅などは使えない。
天秤を2回使えば判定できる。手順は次のとおり。
コインにA、B、Cの名前をつける。あとは次の表に従う。 「○○と△△を比べる」は、○○を天秤の左側の皿に・△△を右側の 皿に乗せて重さを比べるということ。「左」「右」「水平」は それぞれ「左の皿が下がった」「右の皿が下がった」「つりあった」場合を 意味する。
| 1回目 | 2回目 | 結論 | ||
| まず AとBを比べる |
左 | AとCを比べる | 左 | Aが重い |
|---|---|---|---|---|
| 右 | ありえない | |||
| 水平 | Bが軽い | |||
| 右 | AとCを比べる | 左 | ありえない | |
| 右 | Aが軽い | |||
| 水平 | Bが重い | |||
| 水平 | AとCを比べる | 左 | Cが軽い | |
| 右 | Cが重い | |||
| 水平 | ありえない | |||
天秤を3回使えば判定できる。その手順は次のとおり。
12枚のコインにA、B、…、Kの名前をつける。あとは以下の 表に従う。(スペースの都合で1回目の判定結果だけ横に組んでいる)
| スタート: ABCDとEFGHを比べる | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| 水平 | IJとKAを比べる | 左 | ABCEとDIJKを比べる | 右 | ABCEとDIJKを比べる | ||||||
| 水平 | LとAを比べる | 水平 | FとGを比べる | 水平 | FとGを比べる | ||||||
| 水平 | ありえない | 水平 | Hが軽い | 水平 | Hが重い | ||||||
| 左 | Lが重い | 左 | Gが軽い | 左 | Fが重い | ||||||
| 右 | Lが軽い | 右 | Fが軽い | 右 | Gが重い | ||||||
| 左 | IとJを比べる | 左 | AとBを比べる | 左 | DとAを比べる | ||||||
| 水平 | Kが軽い | 水平 | Cが重い | 水平 | Eが重い | ||||||
| 左 | Iが重い | 左 | Aが重い | 左 | ありえない | ||||||
| 右 | Jが重い | 右 | Bが重い | 右 | Dが軽い | ||||||
| 右 | IとJを比べる | 右 | DとAを比べる | 右 | AとBを比べる | ||||||
| 水平 | Kが重い | 水平 | Eが軽い | 水平 | Cが軽い | ||||||
| 左 | Jが軽い | 左 | Dが重い | 左 | Bが軽い | ||||||
| 右 | Iが軽い | 右 | ありえない | 右 | Aが軽い | ||||||
じっさいには問題文はコインの枚数を特定していないので、 コインが何枚のときでもうまく判定できるような一般的な手順を 答えなくては「問題を解いた」とはいえない。 とはいうものの、どこから手をつけたらいいかわからないときは 特定の小規模なケースについて考えることで 何かが見えてくることも多い。そこでしばらく12枚の場合を 考察してみよう。