効率の良い試行錯誤

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

2/64の確率で天秤が傾く。その時、2手で確定する。

62/64の確率でつり合い、残り62枚をコイン1と比較することになる。平均31手で確定する。

平均30手ちょい

方法2

1手で32、2手で16、3手で8、4手で4、5手で2枚に絞り込める。6手で確定。

方法3

2て掛けて、32に絞り込み、かつ偽コインが重いのか軽いのかを特定する

本物コインを1枚足して33枚にし、11枚ずつに分けて比較する。3手で11枚。

本物コインを1枚足して12枚にし、4枚ずつに分けて比較する。4手で4枚。

4枚に絞り込んだ後は、平均1.5手で特定出来る。

平均5.5手で確定できる。また最悪ケースでも6手なので方法2よりも悪くなることはない。

発展問題 偽コインが複数枚になると途端に難しくなる。

偽コインが2枚で、両方重いと分かっているケース

偽コインが2枚で、重いか軽いかわかっていないが、2枚の重さは同じであるケース

偽コイン2枚が合計すると本物コイン2枚と同じ重さである可能性があるケース

偽コインが何枚あるのかわかってないケース

色々な発展問題が考えうる

関連