さて、まず簡単なよく知られた問題から。
「3個のコインがある。見ただけではわからないが、1つだけ軽い偽コインがある。これを天秤を1回だけ使って見つけるにはどうしたらよいか。」
解答:3つのうち2個を選んで1個ずつを左右に乗せれば、一方が軽ければそれが偽コイン、つり合えば残りの1個が偽コインとわかるわけです。
ここで重要なのは、天秤の状態が「右が軽い」「左が軽い」「つり合う」の3通りしか無いから、天秤を1回だけ使うという条件では、最大3つまでしか判別できないという点です。これを考えれば、4個のうち1つだけ軽い偽コインが含まれるときには、考えうる可能性が4通りあるわけですから、絶対に天秤を使う回数が1回では判別は不可能となるわけです。
これを頭に入れて、問題を複雑にしていきます。
「3個のコインがある。見ただけではわからないが、1つだけ軽い偽コインがある。これを天秤を1回だけ使って見つけるにはどうしたらよいか。」
解答:3つのうち2個を選んで1個ずつを左右に乗せれば、一方が軽ければそれが偽コイン、つり合えば残りの1個が偽コインとわかるわけです。
ここで重要なのは、天秤の状態が「右が軽い」「左が軽い」「つり合う」の3通りしか無いから、天秤を1回だけ使うという条件では、最大3つまでしか判別できないという点です。これを考えれば、4個のうち1つだけ軽い偽コインが含まれるときには、考えうる可能性が4通りあるわけですから、絶対に天秤を使う回数が1回では判別は不可能となるわけです。
これを頭に入れて、問題を複雑にしていきます。