2017-09-05 「教科書に正解がない問題」に対しては、自力で試行錯誤して答えを見つけることが必要である。 だが、試行錯誤にも効率の良い試行錯誤と、悪い試行錯誤がある。
問1 64枚のコインがある、1枚だけが偽コインで、他の63枚と重さが違う。手元に重さを測る手段はなく、重さの大小を比較する手段として使える「天秤ばかり」だけがある。どうすれば偽コインを見つけられるか？
解説 「どれが偽コインか」ということは教科書に書いていないので、天秤を使った試行錯誤を繰り返して自分で答えを見つけ出す必要がある。その方法はいくつか考えられる。 この問題への回答には何段階かの質が存在する。
方法1 コイン1とコイン2を天秤で比較。(A)天秤が傾かなければ1,2とも本物であることがわかる。残りのコインをコイン1と比較することで、重さの違うコインを見つけられる。(B)もし1と2の比較で天秤が傾いた場合は、どちらかが偽コインである。「1枚だけが偽コイン」という条件から、残りは全部本物コインであることがわかるので、コイン1と本物コインの重さを比較すればよい。
方法2 天秤に同じ枚数のコインを乗せて、傾けば天秤に乗せている中に偽コインがあり、傾かなければ偽コインはない。これを利用して二分探索をする。(抽象的概念「二分探索」を今回の具体的な問題に応用) 32枚のコインを16枚ずつ天秤に乗せる。傾くなら「乗せた32枚の中に偽コインがある」傾かないなら「乗せなかった32枚の中に偽コインがある」この1回の比較で偽コインの可能性があるコインを半分に絞り込むことができた。同じ手法を繰り返して、16枚、8枚、4枚、2枚と絞り込むことができる。2枚に絞り込んだ後は、片方を正解だと分かっているコインと比較することで確定できる。
方法3 今回の問題では「偽コインの重さが異なることだけがわかっていて、重いのか軽いのかわからない」という「知識の不足」が存在する。これを真っ先に解決する方法も考えられる。32枚のコインを16枚ずつ天秤に乗せて、偽コインのある側の32枚を特定した後、32枚ずつ天秤に乗せる。これによって偽コインが重いのか軽いのかがわかる。 偽コインが重いとすれば、残りの候補は1/3ずつ天秤に乗せることができる。傾いたときには下がった方の1/3に偽コインがあり、つりあった時には乗せなかった1/3に偽コインがある。32枚→11枚→4枚と絞り込む。4枚からは1枚ずつ天秤に乗せることで、1/2の確率で1手で特定し、1/2の確率で2手で特定する。
比較 方法1
発展問題 偽コインが複数枚になると途端に難しくなる。
関連