１２枚のコインのクイズ

「たぬぽの小路」というブログで、とあるクイズが紹介されていました。

それは、次のようなもの。

　１２枚のコインがあり、１枚だけ、重さが僅かに異なるものがある。
　天秤を３回だけ使って特定するにはどうしたら良いか。


これは、難問として挙げられていて、これの前に、初級が載せてある。

　８枚のコインがあり、１枚だけ、重いものが混じっている。
　天秤を２回だけ使って特定するにはどうしたら良いか。



とりあえず、簡単な方の解答から。

８枚から適当に３枚ずつ６枚取り出して、天秤に載せる。
重いものが載った方が下がるから、そこから１枚ずつ２枚取り出して天秤に載せ、傾いた方が答え。傾かなかったら選ばなかった１枚が答え。
そもそも傾かなかったら、選ばなかった２枚を天秤に載せて、傾いた方が答え。

そう、初級の方は、解答に３０秒も要りません。

ちなみに、４枚ずつ天秤に載せる・・・という方法で重い方、重い方と特定していくと、天秤を３回使う事になるので間違いです。


で、本題に入る前に一言。
以下に、解答を載せています、私。
大体、１時間掛かりました。解くのに。
出来れば、解答を見る前に、１時間ほど悩んで頂けると、ボケ防止になるのではないかと思います。

さぁ、紙とペンをご用意下さい。



で、本題に入るわけですよ。

この問題が難しいのは、重さが異なるのは分かっているけれども、重いのか軽いのかは分からないということ。
つまり、天秤が傾いたからと言って、どっちの側に変なコインが混じっているのかは分からないのです。


では、先ず、天秤を無制限に使えるとしたら、どうやって特定しますか？

例えば、こういう方法が考えられます。これが最も多い回数、天秤を使う方法です。
コインを１枚選び出し、天秤の片側に載せます。
もう片側に、残ったコインを１枚ずつ載せて結果を見ていき、傾きが現れたコインが答えです。或いは、２回連続で傾いたら、最初のコインが答えです。
この方法では、最大で１１回、天秤を使う事になり、これが最大値です。

お分かりでしょうが、問題は、重いか軽いかが分からないので、どうやってそれを判定するのか、という点が最も重要になってくるわけです。

そこで、初級で使った、一部残して測る、という方法論が生きてくるわけです。


例えば、１２枚から、４枚ずつ８枚取り出して、天秤に載せます。
もし傾いたら、選んでいない４枚は確実に同じ重さですよね？
傾かなかったら、８枚、同じ重さのものが得られるわけです。これを利用します。

先ず、傾かなかった場合を考えます。
答えは、４枚の中まで絞り込めました。あと２回の天秤で探し出さねばなりません。
４枚から３枚取り出し、答えが含まれない８枚から３枚取り出して天秤で比べます。傾いたら、３枚まで絞り込めました。傾かなければ答えは選ばなかった１枚です。（この１枚が重いか軽いかは問われていませんが、残り１回天秤が残っているので、判定出来ますよね。）
さて、３枚のうち、どれが偽かを調べるわけですが、この時、先ほどどちらに傾いたかを使います。もし、４枚から取り出した方に傾いていれば、答えのコインは重い事になります。そうでなければ、軽い事になります。この判定は重要です。
３枚のコインのうち１枚だけ、重いものが混じっている、どれが重いか、１回だけ天秤を使って特定しろ、という問題は簡単ですよね。
１枚ずつ２枚取り出して、どちらか下がればそれが答え、傾かなければ残りが答えです。
軽い場合は、上がった方が答えという事ですね。

難しいのは、傾いた場合です。
やはり、重いか軽いかの判定を常に考えねばなりません。

そこで、コインを、ＡＢＣＤＥＦＧＨＩＪＫＬとします。説明の為の便宜的な名称です。
ＡＢＣＤを上がった側、ＥＦＧＨを下がった側、ＩＪＫＬは選ばなかった答えのコインを含まない４枚とします。

ＥＦを左側、ＧＨを右側に載せます。又、ＡＢＣＤから適当に１枚（ここではＤとします）を左側に、ＩＪＫＬから適当に１枚（ここではＩとします）を右側に載せます。

傾かなかった場合は、答えはＡＢＣのどれかであり、かつ軽いと分かるので、後は簡単ですね。
左側が下がった場合、ＥＦのどちらかが重いと分かるので、後は簡単です。（Ｄが答えのコインの場合は、ＡＢＣＤが上がった側という仮定に矛盾します。）
右側が下がった場合は、ＧＨのどちらかが重いか、Ｄが軽い事になりますので、後は簡単ですね。

という事で、重いか軽いかの判定と、重さの異なるコインの特定が、同時に僅か３回で出来る事になります。


いや、このクイズは、正直言って、超難問でした・・・。
説明出来るまでに洗練するのが大変でしたよ。

やはり、キーは、答えが重いのか軽いのかを、どう判定していくか、にありますね。


えーと、今回は普段と異なり、答えをオープンで載せてしまいました。
一度答えを知ってしまうと意味がないクイズなので、出来れば、解答を見ずに頭を捻ってもらいたいものです。

ちなみに私は、５円玉を使って考えました。お金で遊ぶのは良くないですかね。


以上。