当サイトを閲覧いただきありがとうございます。 本記事は論理クイズの傑作「帽子のパズル」について解説します。
100人の囚人が一列に並ばされ、それぞれの頭に赤か青の帽子がかぶせられます。各自に見えるのは自分より前に並ぶ人の帽子だけで、自分の帽子と後ろの人の帽子は見えません。列の一番後ろから順に自分の帽子の色を宣言し、当たれば釈放、外れれば処刑。事前に作戦会議が許されるとき、何人まで確実に助けられるでしょうか。直感的には半分がいいところに思えますが、正解はなんと99人。しかも使う道具は「偶数か奇数か」のひとことだけです。
帽子のパズルとは
帽子のパズル（英語では hat puzzle、この版は prisoners and hats puzzle）とは、自分には見えない自分自身の情報を、他人の見え方や発言から推理するタイプの論理クイズの総称です。今回の100人版のルールを整理しておきます。
・100人が一列に並び、全員に赤か青の帽子がかぶせられる。色の内訳は自由（全員赤もありうる） ・各自に見えるのは、自分より前の人の帽子すべて。自分と後ろは見えない ・列の一番後ろの人から順に「赤」か「青」のどちらかだけを宣言する。宣言は全員に聞こえる ・帽子がかぶせられる前に、100人で作戦を相談できる
まず素朴な作戦を考えてみます。何も工夫しなければ、各自が自分の帽子を当てられる確率は2分の1。100人バラバラに賭ければ、期待値で50人しか助かりません。次に思いつくのは、「後ろの人が前の人の帽子の色を宣言してあげる」作戦です。これなら偶数番目の50人は確実に助かりますが、教え役の50人は自分の色と無関係の宣言をするため、やはり運任せになります。確実なのは50人。ここが直感の限界ラインです。
答えは先頭の一言に全情報を圧縮する
正解の作戦はこうです。最初に宣言する一番後ろの囚人が、自分から見える99個の帽子のうち、赤の個数が偶数なら「赤」、奇数なら「青」と宣言する。事前の作戦会議で決めるのは、この取り決めだけです。
2番目の囚人の立場で考えてみましょう。彼には前方98人の帽子が見えています。いま、最初の宣言が「赤」、つまり「前方99人の中の赤は偶数個」だったとします。彼が自分の目で数えた前方98人の赤が奇数個なら、偶奇のつじつまを合わせるために自分の帽子は赤しかありえません。偶数個なら自分は青です。これで2番目は確実に正解できます。
3番目以降も同じです。各自は「最初に宣言された偶奇」と「その後に宣言された赤の個数」と「自分から見える前方の赤の個数」の3つを突き合わせれば、自分の色が一意に決まります。前の人たちが順に正解していくので、聞こえてくる宣言はすべて本当の色。2番目から100番目までの99人は、論理の力だけで全員確実に助かります。
犠牲になりうるのは最初の1人だけで、彼の宣言は自分の色とは無関係の合図なので、当たる確率は2分の1のまま。つまりこの作戦は確実に99人、期待値で99.5人を救います。これが理論上の上限であることも証明できます。最初の1人には自分の帽子の情報がひとかけらも届いていないため、どんな作戦でも100人全員の保証は不可能なのです。
3人の賢者から始まった帰納パズルの系譜
帽子のパズルは古くから「帰納パズル」と呼ばれる一族の看板問題で、その原型として有名なのが3人の賢者の話です。
王様が3人の賢者に目を閉じさせ、「赤い帽子3つと白い帽子2つのどれかをかぶせた」と告げます。実際には3人とも赤。目を開けた賢者たちは互いの帽子は見えますが、自分の帽子は見えません。「自分の色が分かった者は申し出よ」と言われて、しばらく沈黙が続いたあと、いちばん賢い賢者が「私は赤だ」と正解します。
彼の推理はこうです。もし自分が白なら、残る2人は「赤1人と白1人」を見ていることになります。その場合、赤をかぶった側の賢者は「白は2つしかないのだから、目の前の白と合わせて自分が白なら、もう1人がすぐ名乗り出るはず。名乗り出ないなら自分は赤」と推理して答えられたはずです。誰も答えられないという沈黙こそが、自分は白ではないという証拠だったわけです。他人の無言から情報を絞り出すこの技は、後述の青い目の島のパズルにそのまま受け継がれていきます。
そして帽子のパズルは20世紀の終わりに劇的な進化を遂げます。1998年、計算機科学者トッド・エバートが博士論文で発表した「帽子ゲーム」は、数学界の外まで巻き込む流行になり、2001年にはニューヨーク・タイムズ紙が特集記事を組むほどの騒ぎになりました。
エバートの帽子ゲームと誤り訂正符号
エバート版のルールは一見シンプルです。3人のプレイヤーに、コイントスで赤か青の帽子をかぶせます。全員が互いの帽子を見られますが、自分のは見えません。相談は禁止で、合図で一斉に「赤」「青」「パス」のどれかを宣言。誰か1人でも色を当て、かつ誰も外さなければチームの勝ちです。全員パスは負け。
1人が適当に答えて残りがパスすれば勝率50%。これが限界に思えますが、正解の作戦は勝率75%を達成します。作戦は「他の2人が同じ色に見えたら、その逆の色を宣言。違う色に見えたらパス」です。
8通りの帽子の組合せのうち、3人全員が同色になるのは2通りだけ。このときは3人全員が間違った宣言をして負けます。しかし残り6通りでは、少数派の色をかぶった1人だけが宣言し、しかも必ず正解します。つまりこの作戦の本質は、各自の正解率は2分の1のまま変えられないが、間違いを「全員同時に外れる2通り」へ寄せ集め、正解を6通りに薄く分散させることにあります。負けるときは盛大に負け、勝つときは1人の声で静かに勝つ。この偏らせ方が勝率を75%に押し上げるのです。
驚くべきことに、この作戦の一般化はハミング符号という誤り訂正符号の理論そのものであることが分かっています。プレイヤーが7人なら勝率は87.5%まで上がり、その最適戦略は通信データの誤りを自動修復する符号の設計と数学的に同じものになります。遊びのパズルが最先端の符号理論と同じ土俵にあったという発見が、この問題を有名にしました。
パリティという考え方は身の回りで働いている
100人版の鍵だった「偶数か奇数か」は、情報科学ではパリティと呼ばれ、実は私たちの生活を毎日支えています。
クレジットカードの番号には、打ち間違いを検出するためのチェックディジットが1桁含まれています。書籍のISBNやマイナンバーも同様です。ストレージのRAIDは、複数のディスクの内容から計算したパリティを1台分持っておくことで、どれか1台が丸ごと壊れても残りから中身を復元できます。囚人たちの先頭の1人が唱えた合図と、まったく同じ原理です。
このパズルから持ち帰れる発想は2つあると思います。1つは、「全員に必要な情報は、実はすでにほとんど配られている」という見方です。囚人100人に必要な情報は100個ですが、各自の視界に99個分は既に映っており、足りないのは全体の偶奇というたった1ビットでした。共有情報の多いチームでは、連絡すべきなのは全部ではなく差分だけです。もう1つは、エバートのゲームが示した個人の成績とチームの成績は別物という視点です。個々の勝率を1ミリも上げずに、失敗の重なり方を設計するだけでチームの勝率は上げられる。リスクを分散させるか、あえて集中させるかという、ポートフォリオ設計の発想につながります。
よくある疑問
最後に、帽子のパズルについてよく出る疑問に答えておきます。
帽子の色が3色以上になったら作戦は崩れますか？
崩れません。偶奇の代わりに色に0・1・2と番号を振り、見えている番号の合計を3で割った余りを先頭が宣言すれば、まったく同じ理屈で後続全員が自分の色を計算できます。犠牲になりうるのが先頭の1人だけという点も変わりません。色がk色なら余りをkで割って考えるだけで、2色の偶奇はその特別な場合にすぎない、というのが美しいところです。
全員が同時に宣言する場合はどうなりますか？
順番に宣言できないと、前の人の答えという情報が使えないため、99人の保証は不可能になります。ただし面白い変種があり、たとえば2人が互いの帽子を見て同時に宣言する場合、「1人は相手と同じ色、もう1人は相手と違う色を言う」と決めておけば、どんな配色でも必ずどちらか1人は正解します。n色n人でも、各自が担当する余りを分担する同様の作戦で必ず1人は当たるようにできます。全員の正解は狙えなくても、最低1人の正解なら設計で保証できるわけです。
現実のチームプレイに応用できる教訓はありますか？
事前に「合図の意味」を決めておくことの威力だと思います。囚人たちは本番中に相談できませんが、たった1つの取り決めが100人の行動を完全に連携させました。障害対応や災害時の行動計画など、本番中に通信や相談が制限される場面ほど、平時に決めた小さなプロトコルの価値が跳ね上がります。連絡手段を増やすより、少ない連絡で伝わる約束事を作る方が効くことは多いはずです。
関連する論理クイズ・パラドックス
他人の沈黙から推理を積み上げる究極形「青い目の島」、質問の設計で嘘を無力化する「天国と地獄の門番」、そして帰納の推理が意外な結末を招く「抜き打ちテストのパラドックス」の記事です。
まとめ
本記事は論理クイズの傑作「帽子のパズル」について解説しました。如何だったでしょうか。
100人の運命を分けたのは、超能力でも複雑な暗号でもなく、赤い帽子は偶数か奇数かというたった1ビットの取り決めでした。必要な情報のほとんどは既にみんなの視界に配られていて、足りない最後の1ピースだけを先頭の1人が埋める。そしてその同じ原理が、カード番号の誤り検出やRAIDの復元として、今この瞬間も私たちのデータを守っています。
「情報は足りないのではなく、集約されていないだけかもしれない」帽子のパズルが残してくれるこの問いは、チームの情報共有を考えるときにこそ思い出す価値があると思います。
論理クイズ・確率パズルの一覧に戻りたい方は以下のリンクからどうぞ。
それでは次の記事も閲覧いただけると幸いです。
📚 シリーズ：論理クイズ・確率パズル（3/6）
