これが解けたらIQ150!?～囚人の帽子の問題～【TED-Ed】

論理力が試される問題です。
頭脳に自信がある方、数学が得意な方はぜひ挑戦してみてください！

問題

10人の囚人がいます。
彼らは背の高い順に1列に並んでおり、それぞれに黒か白の帽子をかぶせられています。
囚人たちは自分が何色の帽子をかぶっているかわかりません。
また黒と白の帽子がそれぞれ何個あるのかも分かりません。
ただし自分より前に並んでいる囚人の帽子はすべて見ることができます。
ただし、後ろを振り返ってはいけません。
囚人たちは一番後ろの者から順に、自分の帽子の色が何色かを申告していきます。
黒か白以外の言葉を発してはならず、またサインや合図を送ることも禁止されています。
少なくとも9人が正解すれば全員が解放されますが、2人以上間違えると全員助かりません。
囚人たちはこのゲームを始める前に時間を与えられ、どうすれば全員が解放されるかを相談することができます。
さて、どのような戦略をたてれば全員が無事助かるでしょうか？

解答

それでは答えを説明します。
この問題で使うのはずばり『偶奇性(parity)』です。

例えば、囚人たちの帽子の色が、

(後ろ)　白(⑩)　白(⑨)　黒(⑧)　黒(⑦)　白(⑥)　白(⑤)　白(④)　白(③)　白(②)　黒(①)　(前)

となっている場合を考えましょう。カッコ内の数字は囚人の番号を表します。

そして、一番後ろにいる人(囚人⑩)が、
・前の9人の囚人の黒色の帽子が奇数個⇒『黒』と発言
・前の9人の囚人の黒色の帽子が偶数個⇒『白』と発言
とするようにあらかじめ決めておきます。

囚人⑩から見ると、前の9人の帽子のうち黒色は①、⑦、⑧の3個(奇数個)あるので、囚人⑩は『黒』と発言します。
囚人⑩は白色の帽子をかぶっているのでこの解答は不正解になりますが、1人までは間違えてもOKなので問題ありません。

次に囚人⑨が答える番です。
囚人⑨から見ると黒色の帽子が①、⑦、⑧の3個(奇数個)見えます。
そして囚人⑩の発言から、①～⑨のうち黒色の帽子の数は奇数個あることがわかっているので、自分の帽子の色が白であることがわかります。
なので囚人⑨は『白』と答えることができ、正解になります。

そして囚人⑧の順番に移ります。
囚人⑩・⑨の発言より、①～⑧の中に黒色の帽子が奇数個あるはずですが、囚人⑧から見ると黒色の数は①と⑦の2個(偶数個)になります。
ということは自分の帽子の色が黒色だということになります。
なので囚人⑧は『黒』と答え、正解します。

囚人⑦の番になると、囚人⑩・⑨・⑧の解答から①～⑦の中に黒色の帽子は偶数個あることがわかり、かつ自分より前には囚人①の1個(奇数個)しか黒色がないことが分かるので、自分の帽子が『黒』であることが分かります。
これで囚人⑦も正解できます。

囚人⑥～②の順番では、囚人⑩～⑦の発言より黒色が奇数個あることが分かり、そして各自、自分の前にある黒色の帽子の数は囚人①の1個だけ(奇数個)です。
なので⑥～②の囚人はみな自分の帽子の色が『白』だとわかります。

最後に囚人①はそれまでの発言から、残った黒色の帽子の数は奇数個、すなわち1個であることが分かるので、自分の帽子が『黒』と判断できるようになります。

これで全10人のうち9人が自分の帽子の色を正解することができ、全員が無事に解放されます。
今回は上記の1パターンを例にして説明しましたが、これ以外のパターンでもこの方法で解答することができます。

いかがでしたでしょうか？
自力で思いつくことができましたか？
偶奇性を利用することに気づけたら、今回の問題は解けたと思います。
よくできた問題ですね。

動画に出てくる英単語

• overlord:支配者(アーサー・C・クラークのSF小説『幼年期の終わり』が元ネタかな？)
• guard:用心、警戒する
• single-file:一列に
• spare:見逃す
• come up with:思いつく
• parity:偶奇性
• captive:人質
• abduct:誘拐する

関連動画　

これが解けたらGoogleに入れる!?吊り橋の問題【TED-Ed】英語で学ぶ