昨日の晩、咲人さんと話していたら「有名な問題だけど」と言って下記問題を出されまして、派生的な問題はいくつか知ってたんですがこのバージョンは初耳でして、散々悩んだ挙句昨日の段階では時間切れでして、その後風呂入りながら考えてやっと糸口を見つけまして、その結果回答にたどり着いたので以下書くよ。


Q. 12個のおもりのうち、ひとつだけ重さの違うものがある
　　天秤を3回だけ使って重さの違うものを見つけ出してください


A.

[一回目]
　まず、12個のおもりを4個ずつ3つのグループA,B,Cに分け、A4つとB4つを天秤にかける。

　　　　AAAA　　　　BBBB　　　CCCC
　　　￣￣|￣￣　￣￣|￣￣
　　　　　　￣￣￣￣￣
　→釣り合った場合、Cの中に正解のおもりが含まれていることになる。
　　　　Cグループをさらに二個ずつに分け、既に普通の重さであることが判っているAグループの2個と比較。

　　　　[二回目]
　　　　　　AA　　 CC　　CC
　　　　　 ￣|￣　￣|￣
　　　　　　　￣￣￣
　　　　　→釣り合った場合は、てんびんに乗せていなかった二個の中に正解がある。
　　　　　　 釣り合わなかった場合は、てんびんに乗っていた二個の中に正解がある。
　　　　　　 正解を含む方の二個を次の三回目に持ってくる。

　　　　　　　[三回目]
　　　　　　　　　A　　　 C　　　C
　　　　　　　　￣|￣　￣|￣
　　　　　　　　　 ￣￣￣
　　　　　　　　→釣り合った場合は、てんびんに乗せていなかったCが正解。
　　　　　　　　　 釣り合わなかった場合は、てんびんに乗っていたCが正解。


　→一回目で釣り合わなかった場合は、「AAAABBBB」の中に正解のおもりが含まれている。
　　 なお、「AAAA」より「BBBB」の方が重かったものとする。これはつまり、もしAの中に正解があったとしたらそれは普通のおもりより軽いおもりであり、Bに正解があった場合は普通のおもりより重いということになる。
　　 またCはすべて普通のおもりであることが判っている。そこで、二回目は下記のように比較してみる。

　　　　　[二回目]
　　　　　　　AABB　　　　BCCC　　　　AAB
　　　　　　￣￣|￣￣　￣￣|￣￣
　　　　　　　　　￣￣￣￣￣
　　　　　　→釣り合った場合は、てんびんに乗せていなかった「AAB」の中に正解が含まれている。
　　　　　　　 三回目はそのてんびんに乗っていなかった「AAB」を使用して、下記のように比較する。

　　　　　　　　　　[三回目]
　　　　　　　　　　　 AB　　 CC　　　A
　　　　　　　　　　　￣|￣　￣|￣
　　　　　　　　　　 　　￣￣￣
　　　　　　　　　　　→釣り合った場合は、てんびんに乗っていないAが正解。
　　　　　　　　　　　　 左が重かった場合は、てんびんに乗っているBが正解。
　　　　　　　　　　　　 左が軽かった場合は、てんびんに乗っているAが正解。


　　　　　　→二回目で左が重かった場合は、左のてんびんの「BB」の中に正解がある。
　　　　　　　　(Aに正解が含まれていた場合、普通のおもりより軽くなくてはならないから)
　　　　　　　 三回目はその「BB」を比較する。

　　　　　　　　　　[三回目]
　　　　　　　　　　　　B　　 　B
　　　　　　　　　　　￣|￣　￣|￣
　　　　　　　　　　 　　￣￣￣
　　　　　　　　　　　→重い方が正解。(Bは普通のおもりよりも重いはずだから)

　　　　　　→二回目で左が軽かった場合は、左のてんびんの「AA」と右のてんびんの「B」の中に正解がある。
　　　　　　　　(Aは普通のおもりより軽く、Bは普通のおもりより重いはずだから)
　　　　　　　 三回目はその3つを使用して下記のように比較する。

　　　　　　　　　　[三回目]
　　　　　　　　　　　 AB　　 CC　　　A
　　　　　　　　　　　￣|￣　￣|￣
　　　　　　　　　　 　　￣￣￣
　　　　　　　　　　　→釣り合った場合は、てんびんに乗っていないAが正解。
　　　　　　　　　　　　 左が重かった場合は、てんびんに乗っているBが正解。
　　　　　　　　　　　　 左が軽かった場合は、てんびんに乗っているAが正解。

　以上、Q.E.D.



☆解決のポイント

　最初4・4・4のグループに分けるところまではセオリーどおり。そこで釣り合った場合はそのまま特に悩むこともなく正解のおもりまで行き着く。
　釣り合わなかった場合の二回目の試行が難関だった。

　結局てんびんにかけることで得られる結果は「左が重い」「右が重い」「等しい」の三パターンしかないため、残る二回の試行で判別できるのは3パターン×3パターン＝9パターンが限界になる。二回目段階で候補に上がっているおもりは合計8個のため、三回目の試行で「左か右か等しいか」によって答えが変わるように候補のおもりを残しておかなければならない。ということに気づくまですんげー時間かかりました。以上です。