誘導パズル

帰納的パズルは論理パズルであり、マルチエージェント推論の一例であり、その解決法は帰納的原理に沿って進化する。^{[1] [2]}

パズルのシナリオには、常に同じ推論能力を持つ複数のプレイヤーが関与し、同じ推論手順を踏みます。帰納法の原理によれば、最も単純なケースの解決により、次の複雑なケースの解決が明らかになります。帰納法パズルの最も単純なケースが解決されると、その後パズル全体が解決されます。

これらのパズルの典型的な特徴としては、各参加者が他の参加者全員に関する情報（通常は共通知識）を持っているが、自分自身に関する情報を持っていないというパズルが挙げられる。また、通常、参加者が互いの知性を信頼できることを示唆する何らかのヒントが与えられる。つまり、参加者には心の理論の能力がある（「参加者全員がmodus ponens を知っている」ことは共通知識である）。^[3]また、参加者の無作為な行動は、その参加者の知識不足を非言語的に伝えるものであり、無作為な行動を観察した参加者全員にとって知識不足となる。

泥だらけの子供たちのパズルは、認識論的論理に関する科学文献で最も頻繁に登場する帰納的パズルです。^{[4] [5] [6]}泥だらけの子供たちのパズルは、よく知られている賢者パズルや浮気妻/夫パズルのバリエーションです。^[7]

帽子パズルは、1961年にまで遡る誘導パズルのバリエーションです。 ^[8]多くのバリエーションでは、帽子パズルは囚人という文脈で説明されています。^{[9] [10]}他の場合には、帽子パズルは賢者という文脈で説明されています。^{[11] [12]}

注意深く聞いている子供たちのグループに、彼らのうちの何人かは顔が泥だらけだと告げる。子供たちは皆、他の子供たちの顔は見えるが、自分の顔が泥だらけかどうかは分からない。子供たちには、泥だらけの顔の子供は前に出なければならないが、きれいな顔の子供が前に出たら罰せられると告げられる。3つ数えると、自分の顔が泥だらけだと信じている子供は全員同時に前に出なければならない。他の子供に何らかの方法で合図をした子供は罰せられる。泥だらけの顔の子供が前に出なかった場合、このプロセスが繰り返される。^{[4] [5] [13]}

各子供が完全な論理を持ち、他の子供も完全な論理を持っていることを知っていると仮定すると、泥だらけの顔 ( ) を持つすべての子供は の番で一緒に前に出ます。子供たちは、自分の顔が泥だらけかどうかによって異なる情報を持っています。 の各メンバーは泥だらけの顔を見て、泥だらけの顔が自分だけであれば、それらの子供たちが の番で前に出ることを知っています。それが起こらない場合、 の各メンバーは、自分も のメンバーであることを知っており、 の番で前に出ます。 のメンバーでない各人は泥だらけの顔を見て、少なくとも の番になるまでは誰も前に出ないと予想します。 ${\displaystyle X}$${\displaystyle X}$${\displaystyle X}$${\displaystyle X-1}$${\displaystyle X-1}$${\displaystyle X}$${\displaystyle X}$${\displaystyle X}$${\displaystyle X}$${\displaystyle X}$${\displaystyle X}$

アリスとボブという2人の子供がいて、アリスだけが泥だらけ( )であると仮定します。アリスは「何人か」の子供の顔が泥だらけであることは知っていますが、他の子供の顔は誰も泥だらけではないことを知っているため、自分の顔は泥だらけであるに違いなく、1ターン目に前に進み出ます。アリスの泥だらけの顔を見たボブは、アリスが前に進む(つまり、自分の顔はきれいであるに違いないことを示す)まで、1ターン目に自分の顔が泥だらけかどうかを知るすべがありません。アリスとボブの両方が汚れている場合( )、それぞれが のときのボブの位置にあります。つまり、どちらも1ターン目に前に進むことはできません。しかし、2ターン目までにボブはアリスが自分の顔が泥だらけであることに気づいたに違いないことを知っているので(1ターン目に前に進まなかったため)、2ターン目に前に進み出ます。同じ論理を使用して、アリスも2ターン目に前に進み出ます。 ${\displaystyle X=1}$${\displaystyle X=2}$${\displaystyle X=1}$

3 人目の子供、チャーリーがいるとします。アリスだけが泥だらけ ( ) なら、アリスは泥だらけの顔を見ないので、1 ターン目に前に進み出ます。アリスとボブの両方が泥だらけ ( ) なら、どちらも 1 ターン目に前に進むことはできませんが、2 ターン目までに相手が泥だらけの顔を見たことがわかります (その顔がチャーリーの顔でないことはわかります)。そのため、自分の顔は泥だらけに違いなく、2 ターン目に前に進み出ます。チャーリーは 2 つの泥だらけの顔を見て、2 ターン目にアリスとボブの両方が前に進む (自分の顔がきれいであることを示す) まで、自分の顔が泥だらけかどうかわかりません。3 人全員が泥だらけ ( ) なら、次の場合にそれぞれがチャーリーの立場になります。2 人が 2 ターン目に前に進まなかった場合、それぞれが相手が 2 つの泥だらけの顔を見たので自分の顔も泥だらけに違いないとわかり、3 ターン目にそれぞれが前に進み出ます。 ${\displaystyle X=1}$${\displaystyle X=2}$${\displaystyle X=3}$${\displaystyle X=2}$

泥だらけの子供は順番に前に進むことが証明されている。^{[4] [14]}${\displaystyle X}$${\displaystyle X}$

泥だらけの子供たちのパズルは、ゲーム理論からの逆方向帰納法を使って解くこともできます。^{[13]泥だらけの子供たちのパズルは、}不完全情報ゲームとして表すことができます。すべてのプレーヤーには、後ろに下がるか前に進むかの 2 つのアクションがあります。ゲームの開始時に、自然に動きがあり、それによって顔が泥だらけの子供とそうでない子供が決まります。子供たちは、非協力ゲームのようにコミュニケーションをとりません。すべてのストロークは、子供たちによる同時移動です。これは、長さに制限のない順次ゲームです。ゲーム理論的解決には、いくつかの追加の仮定が必要です。

1. すべての子供は合理的であり、すべての子供の合理性は共通の知識です。つまり、アリスは合理的であり、アリスはボブが合理的であることを知っており、アリスはボブがチャーリーが合理的であることを知っていることを知っており、逆もまた同様です。
2. 泥だらけの顔にならないで前に進むと、大きなペナルティを受けることになります。
3. 泥だらけの顔で前に進むとご褒美がもらえます。
4. 1 回のストロークごとに、いずれかの子供が前に出るまで、すべての子供に対してマイナー マイナス ペナルティ (つまり割引係数)が発生します。マイナー ペナルティの倍数は、常に、大きなペナルティよりも悪は小さくなります。

アリスだけが泥だらけなら、最後の仮定によりアリスが躊躇するのは不合理です。アリスとボブが泥だらけなら、ボブが最初のストロークの後に後ろに留まる唯一の理由は、泥だらけの顔なしで前に進むという大きなペナルティを受けることを恐れているからだとアリスは知っています。泥だらけの子供たちの場合、小さなペナルティを何倍も受ける方が、大きなペナルティを受けるよりまだましです。 ${\displaystyle X}$${\displaystyle X}$

王は国で最も賢い3人を宮廷に呼び、誰が新しい顧問になるかを決めさせた。王は彼らの頭に帽子をかぶせた。各賢者は他の帽子は見えるが、自分の帽子は見えないようにするためである。それぞれの帽子は白か青であった。王は賢者らに、少なくとも1人は青い帽子をかぶることを約束した。言い換えれば、青い帽子は1つ、2つ、または3つあっても、ゼロではないということである。王はまた、この競争は3人全員に公平に行われると宣言した。賢者らは互いに話すことも禁じられた。王は、最初に立ち上がって自分の帽子の色を正しく言った者が新しい顧問になると宣言した。賢者らは長い間座っていたが、1人が立ち上がって正しく答えた。彼は何と言い、どうやって答えを導き出したのだろうか？^[15]

「王の賢者」は最も単純な帰納的パズルの 1 つであり、使用される方法を最も明確に示すものの 1 つです。

• 青い帽子が 1 つあったとします。その帽子をかぶった人は白い帽子を 2 つ見ます。王様は青い帽子が少なくとも 1 つあると指定しているので、その賢者はすぐに自分の帽子の色を知ることができます。しかし、他の 2 人は青い帽子と白い帽子を 1 つずつ見ますが、観察からすぐに情報を推測することはできません。したがって、このシナリオは、競争は各人に公平であるという王様の指定に違反します。したがって、青い帽子は少なくとも 2 つある必要があります。
• では、青い帽子が 2 つあったと仮定します。青い帽子をかぶった賢者はそれぞれ、青い帽子と白い帽子を 1 つずつ見ることになります。彼らがすでに帽子が 1 つしかないはずがないことに気づいていると仮定すると (前のシナリオを使用)、彼らは青い帽子が少なくとも 2 つあるはずであることを知っているので、それぞれが青い帽子をかぶっていることをすぐに理解するでしょう。しかし、白い帽子をかぶった賢者は青い帽子を 2 つ見ても、観察からすぐに情報を推測することはできません。したがって、このシナリオは、競争が各人に公平であるという仕様にも違反します。したがって、青い帽子は 3 つあるはずです。

青い帽子は 3 つあるはずなので、それを最初に理解した人が立ち上がって「青」と言います。

代替の解決法: これは、競争が各人に公平であるというルールを必要としません。むしろ、彼ら全員が賢明な人であり、解決にたどり着くまでに時間がかかるという事実に依存しています。シナリオは 3 つしかありません。青い帽子 1 つ、青い帽子 2 つ、または青い帽子 3 つです。青い帽子が 1 つだけの場合、その帽子をかぶっている人は白い帽子 2 つを見て、すぐに青い帽子をかぶらなければならないことがわかるので、立ち上がってすぐにそのことを発表します。これが発生していないので、青い帽子は少なくとも 2 つあるはずです。青い帽子が 2 つある場合、青い帽子をかぶっている人のどちらかが向こうを見て青い帽子 1 つと白い帽子 1 つを見るものの、自分の帽子の色はわかりません。青い帽子をかぶっている最初の人が自分の帽子が白い帽子だと思っていたら、もう 1 人の青い帽子をかぶっている人が白い帽子 2 つを見ていることがわかるので、2 番目の青い帽子をかぶっている人はすでに立ち上がって青い帽子をかぶっていることを発表しているはずです。したがって、これが起こらなかったため、青い帽子を最初にかぶった人は自分が青い帽子をかぶっていることを知っており、立ち上がってこれを発表することができます。青い帽子が 1 つまたは 2 つであれば簡単に解決でき、誰もすぐに立ち上がらなかったため、全員が青い帽子をかぶっているに違いありません。

ジョゼフィーヌ王国では、女性は結婚する前に論理試験に合格しなければなりません。^{[16]既婚女性は自分の夫}以外の王国の男性の貞操を知っており、エチケットでは女性に夫の貞操について教えてはならないとされています。また、王国のどの家で発砲された銃声も、他のどの家でも聞こえます。ジョゼフィーヌ女王は、王国で少なくとも1人の不貞な男性が発見されたこと、そして夫の不貞を知っている女性は、夫の不貞を発見した翌日の真夜中に夫を射殺しなければならないことを発表しました。妻たちはどうやってこれをやり遂げたのでしょうか。

ジョセフィーンの問題は、一般的なケースのもう一つの良い例です。

• 不貞な夫が 1 人だけなら、王国のすべての女性がそれを知っています。ただし、妻は誰もが貞淑であると信じているからです。そのため、女王から不貞な男性が存在すると聞くと、彼女は自分の夫が不貞であるとすぐにわかり、彼を撃ち殺します。
• 不貞な夫が 2 人いる場合、どちらの妻も不貞な夫は 1 人 (もう 1 人) だけだと信じています。したがって、上記のケースが当てはまり、もう 1 人の夫の妻が翌日の真夜中に夫を撃つだろうと予想します。銃声が聞こえないと、上記のケースは当てはまらず、不貞な夫は 1 人以上いるはずであり、(他の全員が貞潔であることを知っているので) 余分の 1 人は自分の夫に違いないと気付きます。
• 不貞な夫が 3 人いる場合、それぞれの妻は不貞な夫は 2 人だけだと信じているため、上記のケースが当てはまり、2 日目に両方の夫が撃たれると予想します。銃声が聞こえないと、上記のケースは当てはまらず、不貞な夫は 2 人以上いるはずであり、以前と同様に自分の夫が唯一の追加候補であることに気付きます。
• 一般的に、不貞な夫がn人いる場合、それぞれの妻は不貞な夫がn-1人いると信じ、 n-1日目の真夜中に銃声が聞こえると予想します。銃声が聞こえない場合、妻たちは自分の夫がn人目だったと知ります。

この問題は、浮気夫問題、不貞妻問題、泥だらけの子供問題としても知られています。これは、ブルーアイズ問題と論理的に同一です。

この問題は、CL Liuの古典的な教科書『離散数学の要素』にもブラックハットとホワイトハットの問題として登場します。^[17]

論理学者の秘密会議では、マスター論理学者が出席者の頭にバンドを取り付けました。他の人は見えるのですが、本人は見えませんでした。バンドの色は様々でした。論理学者は皆輪になって座り、マスターは森の中で定期的にベルを鳴らすように指示しました。論理学者が自分の額の色を知った瞬間、次のベルでその場を立ち去らなければなりませんでした。彼らは話したり、鏡やカメラを使ったり、論理を使ってバンドの色を判定したりしないように指示されました。偽者が会議に潜入していた場合に備えて、時間通りに退出できなかった者は、適切な時間にぶっきらぼうに追い出されました。同様に、早く退出しようとした者は、ぶっきらぼうにその場に留められ、適切な時間に追い出されました。マスターは、真の論理学者なら誰でもこのパズルを解くことは不可能ではないと述べて、グループを安心させました。彼らはどうやってそれをやったのでしょうか? ^[18]

論理学者の大会でのアリスは、一般帰納法に論理の飛躍を加えたものです。

• 論理の飛躍:円周上には、どの色も少なくとも 2 回は出現しなければなりません。これは、マスターが、論理学者なら誰でもこのパズルを解くことは不可能ではないと述べたためです。円周上に 1 色しか出現しない場合、その色を所持する論理学者は、問題にその色が存在することすら知る術がなく、答えを出すことは不可能です。
• 各論理学者は円の周りを見て、各色を見た回数を数えることができます。あなたが論理学者の 1 人で、別の色を 1 回だけ見たとします。各色は円の周囲に少なくとも 2 回は存在するはずなので、単色が存在する唯一の説明は、それが自分のバンドの色であるということです。同じ理由で、そのような単色は 1 つしか存在できないので、最初のベルで終了します。
• 同様に、他の色を一度しか見ていない論理学者は、自分の色を判断でき、威厳を持って退場するか、侵入者として追い出されるかのいずれかになります。同様に、その色の帯が 2 つしかない色は、最初のベルが鳴った後に排除されます。その後、残っている色には少なくとも 3 つの帯がなければなりません。
• 一度はどの色も見えなかったが、二度は色が見えたとします。この色のバンドがこれだけなら、この二人の論理学者は最初のベルで去るべきでした。彼らが去らなかったのは、あなた自身のバンドが同じ色だからで、二度目のベルで去ることができるからです。
• したがって、すべての論理学者は、自分が離脱すると予想していた特定の色のグループが離脱に失敗するまで監視することになります。そうすると、その色を持っていることがわかり、次のベルで離脱することになります。
• 1 色だけ残った場合、その色の子たちは次のベルで全員去ります。なぜなら、他の色を持つことはできないとわかっているからです (そうなると、自分の色を知ることが不可能になるからです)。

何人かのプレイヤーがそれぞれ帽子をかぶっており、その色は様々である。プレイヤーは少なくとも他のプレイヤーの帽子の色は見えるが、自分の帽子の色は見えない。コミュニケーションが極度に制限されているか全くない場合、プレイヤーの何人かは自分の帽子の色を推測しなければならない。問題は、プレイヤーが見た帽子と他のプレイヤーの行動に基づいて自分の帽子の色を決定する戦略を見つけることである。いくつかのバージョンでは、プレイヤーは最初に正しく推測することを競い合い、他のバージョンでは、協力して正しい推測の確率を最大化するために事前に戦略を立てることができる。^[19]

一つのバリエーションは、トッド・エバートが1998年にカリフォルニア大学サンタバーバラ校で博士 論文を発表したことで、新たな注目を集めました。^{[20]これは}協力ゲームに関する戦略問題であり、代数的符号理論と関連があります。^[21]

3 人のプレーヤーはそれぞれ赤い帽子か青い帽子を受け取ることになります。3 人は互いに向き合って輪になって立ち、他のプレーヤーが赤い帽子をかぶっているのを見たら手を挙げます。最初に自分の帽子の色を正しく当てた人が勝ちです。

3 人のプレーヤー全員が手を挙げます。プレーヤーが数分間お互いを見て推測しなかった後、1 人のプレーヤーが「赤」と宣言して勝ちます。勝者はどのようにそれをしたのでしょうか。そして、全員の帽子の色は何色でしょうか。

まず、もし二人が青い帽子をかぶっていたら、全員が手を挙げることはないだろう。次に、プレイヤー1がプレイヤー2の青い帽子とプレイヤー3の赤い帽子を見たら、プレイヤー1は自分の帽子が赤いに違いないとすぐに分かるだろう。したがって、青い帽子を見たプレイヤーは誰でもすぐに推測できる。最後に、勝者は誰もすぐに推測しないので、青い帽子は存在せず、すべての帽子が赤いに違いないと分かる。^[22]

すべてのプレイヤーが推測しなければならないが、推測するタイミングは自由に選択できる場合、すべての帽子が同じ色でない限り、すべてのプレイヤーが正しく推測できるようにする協力戦略があります。各プレイヤーは次のように行動する必要があります。

1. 見える青い帽子の数bと赤い帽子の数 r を数えてください。
2. b秒またはr秒のうち、いずれか早い方だけ待機します。
3. まだ誰も発言していない場合は、赤い帽子よりも青い帽子が少ない場合は自分の帽子は青、青い帽子よりも赤い帽子が少ない場合は自分の帽子は赤であると推測します。
4. まだ話していない場合は、あなたの帽子が最初に話す人の帽子と反対の色になっていると推測してください。

合計で青い帽子がB 個、赤い帽子がR 個あるとします。3 つのケースがあります。

B = Rの場合、青い帽子をかぶっているプレイヤーはB−1 個の青い帽子とB 個の赤い帽子を見るので、B −1 秒待ってから青い帽子をかぶっていることを正しく推測します。同様に、赤い帽子をかぶっているプレイヤーはR −1 秒待ってから赤い帽子をかぶっていることを正しく推測します。つまり、すべてのプレイヤーが同時に正しい推測をすることになります。

B < Rの場合、青い帽子をかぶっている人はB −1 個の青い帽子とR 個の赤い帽子を見ることになります。一方、赤い帽子をかぶっている人はB 個の青い帽子とR −1 個の赤い帽子を見ることになります。B −1 < B ≤ R −1 なので、青い帽子をかぶっているプレイヤーが最初に発言し、自分の帽子が青いと正しく推測します。次に、他のプレイヤーは自分の帽子が赤いと正しく推測します。

R < Bの場合も同様です。

4人の囚人が犯罪で逮捕されたが、裁判官は彼らが論理パズルを解くことができれば刑罰を免除すると提案した。 ^[23]

3 人の男が一列に並びます。A は壁を向き、B は A を向き、C は B と A を向きます。4 人目の男は壁の後ろに置かれます。4 人全員が帽子をかぶっています。黒い帽子が 2 つと白い帽子が 2 つあり、囚人はそれぞれいずれかの帽子をかぶっています。囚人はそれぞれ自分の前にある帽子しか見えず、自分の後ろにある帽子は見えません。スクリーンの後ろにいる 4 人目の男は、他の囚人を見ることも、他の囚人に見られることもできません。囚人同士のコミュニケーションは許可されていません。自分の頭にかぶっている帽子の色を 100% 確実に (推測せずに) 当てることができた囚人は、それを発表しなければならず、4 人の囚人全員が解放されます。

囚人たちは、同じ色の帽子は 2 つしかないことを知っています。したがって、C が A と B が同じ色の帽子をかぶっているのに気づいた場合、C は自分の帽子は反対色であると推測します。しかし、A と B の帽子の色が違っていたら、C は何も言えません。鍵となるのは、囚人 B が適切な間隔をあけ、C がどうするかを知った後、C が何も言わなければ A と B の帽子は違うに違いないと推測できることです。A の帽子が見えれば、彼は自分の帽子の色を推測できます。

このタイプの多くのパズルと同様に、このパズルの解決は、すべての参加者が適切な推論を行えるほど合理的かつ知的であるという仮定に基づいています。

このパズルを解いた後、囚人 C の意味のある沈黙が「コミュニケーション禁止」ルールに違反しているかどうかを考えることによって、コミュニケーションの本質についてある程度の洞察を得ることができます (コミュニケーションは通常「情報の伝達」と定義されます)。^{[引用が必要]}

このバリエーションでは、囚人が 3 人いて、帽子が 3 つあります。各囚人には、赤または青のランダムな帽子が割り当てられます。各人は、他の 2 人の帽子を見ることができますが、自分の帽子は見えません。合図で、各自が自分の帽子の色を推測するか、パスする必要があります。少なくとも 1 人が正しく推測し、誰も間違って推測しなかった場合 (パスは正解でも不正解でもありません)、解放されます。

このパズルには100%勝てる戦略はないが、75%の確率で勝つことができる。帽子の色をビットとして考えると、この問題はハミング符号などの符号理論を使って解くことができる。^[24]

このパズルのバリエーションでは、囚人たちは黒い帽子が 2 つと白い帽子が 2 つあること、そして A と B の間に壁があることを知っていますが、囚人 B、C、D は目の前に誰がいるのかを見ることができます。つまり、D は B、C、壁を見、B は壁を見、C は B と壁を見ます。(A はやはり見えず、黒い帽子の 1 つをかぶっているだけです。) どのようにして、意思疎通をせずに全員の色を推測できるのでしょうか。

2 つのケースがあります。自明なケースでは、4 人の囚人のうち 2 人が黒い帽子をかぶっています。他の 2 人の囚人はそれぞれ、1 人の囚人が色の違う帽子をかぶっているのがわかります。非自明なケースでは、4 人の囚人のうち 2 人が同じ色の帽子をかぶっていますが、A と C は黒い帽子をかぶっています。しばらくすると、4 人の囚人全員が、D と B が自分の帽子の色を言えなかったため、A と C が黒い帽子をかぶっているに違いないと推測できるはずです。

別のバリエーションでは、3 人の囚人と、色のわかっている 5 つの帽子 (この例では、黒 2 つと白 3 つ) だけが使用されます。3 人の囚人は、A が前に、C が後ろに、正面を向いて一列に並ぶように指示されます。黒い帽子が 2 つ、白い帽子が 3 つあることが伝えられます。次に、各囚人の頭に帽子を 1 つずつかぶせます。各囚人は、自分の前にいる人の帽子しか見えず、自分の帽子は見えません。自分の帽子の色を正しく答えることができた最初の囚人が解放されます。囚人同士の意思疎通は許可されません。

A が黒い帽子をかぶっていると仮定します。

• B も黒い帽子をかぶっている場合、C は目の前にある 2 つの黒い帽子を見て、B が白い帽子をかぶっていることがすぐにわかります。
• B が白い帽子をかぶっている場合、C は彼の帽子の色を判別できません (黒と白があるため)。したがって、B は A の黒い帽子と C の反応のなさから、彼 (B) が白い帽子をかぶっていることをすぐに推測できます。

したがって、A がブラックハットをかぶっている場合、B または C からの反応はかなり速くなります。

A が白い帽子をかぶっていると仮定します。

• C は 2 つの黒い帽子が見えないので、自分の帽子の色を判別できません。
• B は白い帽子しか見ていないので、自分の帽子については何もわかりません。

この場合、A、B、C はしばらく沈黙しますが、C と B がしばらく沈黙しているため、A は最終的に自分が白い帽子を持っているに違いないと推測します。

前述のように、全部で白い帽子が 3 つ、黒い帽子が 2 つあり、3 人の囚人はこれを知っています。このなぞなぞでは、3 人の囚人全員が非常に賢く、非常に頭が良いと想定できます。C が自分の帽子の色を推測できなかったのは、白い帽子が 2 つ、または各色 1 つずつ見えたためです。黒い帽子が 2 つ見えたなら、白い帽子をかぶっていると推測できたはずです。

このバリエーションでは、10 人の囚人と 10 個の帽子があります。各囚人には赤または青のランダムな帽子が割り当てられますが、各色の帽子の番号は囚人にはわかりません。囚人は一列に並び、各自は自分の前の帽子は見えますが、後ろの帽子は見えません。列の最後尾の囚人から始めて、前に進みながら、各囚人は順番に「赤」または「青」の単語を 1 つだけ言わなければなりません。単語が帽子の色と一致した場合は解放され、一致しなかった場合はその場で殺されます。同情的な警備員が 1 時間前にこのテストについて警告し、規定のルールに従うことで 10 人の囚人のうち 9 人が確実に生き残り、1 人が 50/50 の確率で生き残る計画を立てることができると伝えます。目標を達成するための計画は何ですか?

囚人たちは、最初の囚人が奇数の赤い帽子を見たら「赤」と言うことに同意します。こうすることで、後ろの囚人が答えた後、他の 9 人の囚人は自分の帽子の色を知ることができます。

前回と同様に、囚人は 10 人で帽子も 10 個あります。各囚人には赤か青の帽子がランダムに割り当てられますが、各色の帽子の番号は囚人にはわかりません。囚人は、他の人の帽子は見えるが自分の帽子は見えないように部屋に配置されます。今、囚人はそれぞれ同時に「赤」か「青」の単語を 1 つだけ言わなければなりません。単語が自分の帽子の色と一致した場合、囚人は解放されます。十分な数の囚人が自由を取り戻した場合、他の囚人を救出できます。同情的な警備員が、このテストの 1 時間前に囚人に警告します。定められた規則に従って計画を立てることができれば、10 人の囚人のうち 5 人は確実に解放され、他の囚人を救出できます。目標を達成するための計画は何ですか?

囚人たちはペアになります。囚人たちのペア (A、B) のうち、A は B の頭に見える色を言い、B は A の頭に見える反対の色を言います。その後、両者が同じ色の帽子をかぶっている場合は A が解放され (B は解放されません)、色が異なる場合は B が解放されます (A は解放されません)。合計で 5 人の囚人が正しく答え、5 人が間違っています。これは、ペアが誰が A で誰が B であるかを意思疎通できると仮定していますが、これは許可されない可能性があります。

あるいは、囚人たちは 5 人ずつの 2 つのグループを作ります。1 つのグループは赤い帽子の数が偶数であると想定し、もう 1 つのグループは赤い帽子の数が奇数であると想定します。聴覚を使ったバリエーションと同様に、この想定から帽子の色を推測できます。正確に 1 つのグループが正解なので、5 人の囚人が正しく答え、5 人の囚人は間違って答えます。

囚人たちは 5 人以上の囚人の釈放を保証する戦略を見つけることができないことに注意してください。実際、1 人の囚人の場合、正解を言う帽子の色の分布は、正解を言わない帽子の色の分布と同じ数あります。したがって、6 人以上の囚人が正解を言う帽子の色の分布は、4 人以下の囚人が正解を言う帽子の色の分布と同じ数あります。

このバリエーションでは、数えられるほど無限の数の囚人が、それぞれ赤か青の帽子をかぶり、一列に並びます。各囚人は列の先頭から背を向けており、自分の前にある帽子はすべて見えますが、後ろにある帽子はまったく見えません。列の先頭から始めて、各囚人は自分の帽子の色を正しく特定しなければ、その場で殺されます。前と同じように、囚人は事前に会う機会がありますが、前とは異なり、列に並ぶと、他の囚人の言うことを聞くことはできません。問題は、殺される囚人が有限の数だけになるようにする方法があるかどうかです。

選択公理を受け入れ、囚人それぞれが（非現実的な）無数個の情報を記憶し、無数個無限個の計算複雑性を伴う計算を実行する能力を持っていると仮定すると、答えは「はい」です。実際、帽子に無数個の異なる色と無数個の囚人を許容したとしても、選択公理は、各囚人が他のすべての囚人の帽子（列の先頭の囚人だけではなく）が見えるか、少なくとも各囚人が他の帽子を有限個以外すべて見ることができるという条件で、有限個の囚人だけが死ぬことを保証する解を提供します。2色の場合の解は次のようになります。無数個色の場合の解も基本的に同じです。

列に並んでいる囚人たちは 0 と 1 の列を作ります。0 は青、1 は赤を表します。列に並べられる前に、囚人たちは、自分たちが並べられる可能性のあるすべての列に対して、次の同値関係を定義します。2 つの列は、有限回数入力した後に同一である場合に同等です。この同値関係から、囚人たちは同値クラスのコレクションを取得します。選択公理を想定すると、各同値クラスから 1 つずつ、代表的な列の集合が存在します (ほとんどすべての特定の値を計算することは不可能ですが、選択公理により、何らかの値のセットが存在することが示唆されるため、囚人たちは神託にアクセスできると想定します)。

囚人たちは列に並べられると、有限個を除くすべての帽子を見ることができるため、実際の帽子の列がどの同値類に属するかがわかります。(これは、各囚人が一致するものを見つけるために無数に無限回の比較を実行でき、各クラス比較には無数に無限回の個別の帽子比較が必要であると仮定しています)。次に、適切な同値類の代表列にいるかのように、自分の帽子の色を推測します。実際の列と代表列は同じ同値類にあるため、有限数N人の囚人以降は、それらのエントリーは同じになります。これらの最初のN人の囚人以降の囚人はすべて救われます。

囚人は自分の帽子の色に関する情報を持たず、どんな色でも同じ推測をするため、各囚人が殺される可能性は 50% です。無限の数の囚人がそれぞれ殺される可能性が均等であるにもかかわらず、殺されるのは有限の数だけであることは矛盾しているように思えるかもしれません。この矛盾を解決するには、各囚人の推測を決定するために採用されている関数が測定可能な関数ではないという事実にあります。

これを理解するには、殺される囚人がゼロの場合を考えてみましょう。これは、実際のシーケンスが選択された代表シーケンスの 1 つである場合に限り発生します。0 と 1 のシーケンスを 0 から 1 までの実数の 2 進表現と見なすと、代表シーケンスは測定不可能なセットを形成します。(このセットはVitali セットに似ていますが、唯一の違いは、同値類がすべての有理数ではなく有限の 2 進表現を持つ数に関して形成されることです。)したがって、殺される囚人がゼロというイベントに確率を割り当てることはできません。他の有限数の囚人が殺される場合、各代表の有限の数のバリエーションに対応する議論も同様です。

このバリエーションは、囚人が他の囚人が呼ぶ色を聞くことができる点を除いて、前のバリエーションと同じです。問題は、最悪の場合に囚人の死者を最小限にするための最適な戦略は何かということです。

結局、囚人たちに他の囚人たちが呼ぶ色を聞かせれば、最初の囚人を除くすべての囚人の命を保証できることが判明した。最初の囚人は50%の確率で死亡する。

これを行うには、上記と同じ同値関係を定義し、各同値クラスから再び代表シーケンスを選択します。ここで、各クラスのすべてのシーケンスに 0 または 1 のラベルを付けます。まず、代表シーケンスに 0 のラベルを付けます。次に、代表シーケンスと偶数桁異なるシーケンスに 0 のラベルを付け、代表シーケンスと奇数桁異なるシーケンスに 1 のラベルを付けます。このようにして、1 桁だけ異なる 2 つのシーケンスには反対のラベルが付くという重要な特性を持つ、考えられるすべての無限シーケンスに 0 または 1 のラベルを付けました。

さて、看守が最初の人に色、または私たちの新しい解釈では 0 か 1 を言うように頼むとき、彼は単に自分が見たシーケンスのラベルを呼ぶだけです。この情報があれば、彼の後続の人は自分の帽子の色を正確に判断できます。2 番目の人は、最初の人が見たシーケンスの最初の数字以外すべてを見ています。したがって、彼の知る限り、最初の人がラベルを付けていた可能性のあるシーケンスは 2 つあります。1 つは 0 で始まり、もう 1 つは 1 で始まります。私たちのラベル付けスキームにより、これらの 2 つのシーケンスには反対のラベルが付けられるため、最初の人の発言に基づいて、2 番目の人は最初の人が見た 2 つの可能性のある文字列のどちらであるかを判断でき、したがって自分の帽子の色を判断できます。同様に、列の後の人は全員、自分の帽子の色に対応する数字を除くシーケンスのすべての数字を知っています。彼は、自分の前にいる人たちは呼ばれたので知っていますが、自分の後にいる人たちは見えるので知っています。この情報があれば、彼は最初の人が呼んだラベルを使用して自分の帽子の色を判断できます。したがって、最初の人を除く全員が常に正しく推測します。

エバートのバージョンの問題では、推測するすべてのプレーヤーは、事前に決められた同じ時間に推測する必要がありますが、すべてのプレーヤーが推測する必要はありません。すべてのプレーヤーが正しく推測できるわけではないため、少なくとも 1 人のプレーヤーが推測し、推測するすべてのプレーヤーが正しく推測した場合、プレーヤーは勝ちます。プレーヤーは、勝つ可能性を最大化するにはどうすればよいでしょうか。

このバージョンの帽子問題を解くための 1 つの戦略は、データ伝送のエラーを検出して修正するために一般的に使用されるハミング コードを使用します。パズル構成のプレーヤーの数に応じて、勝利の確率は 50% よりもはるかに高くなります。たとえば、プレーヤーが 7 人の場合、勝利の確率は 87.5% になります。

同様の戦略をチームサイズN = 2 ^k −1に適用し、勝率 (2 ^k -1)/2 ^{kを達成できます。したがって、ハミングコード戦略では、} Nの値が大きいほど勝率が高くなります。

このバージョンの問題は、個々の推測が正解になる確率が 50% です。ただし、ハミング コード アプローチは、間違った推測を特定の帽子の分布に集中させることで機能します。場合によっては、すべてのプレーヤーが間違った推測をしますが、他の場合には、1 人のプレーヤーだけが正しい推測をします。推測の半分は依然として間違っていますが、これによりプレーヤーは 50% 以上の確率で勝利します。

3 人のプレイヤーによるこのタイプの解決法の簡単な例は、参考になります。3 人のプレイヤーの場合、8 つの可能性があります。そのうちの 2 つは、すべてのプレイヤーが同じ色の帽子をかぶっています。残りの 6 つは、2 人のプレイヤーが 1 つの色を持ち、もう 1 人のプレイヤーが別の色を持っています。

プレイヤーは、次の戦略により、後者の場合（75% の確率）に勝利することを保証できます。

1. 異なる色の帽子が 2 つあることに気づいたプレイヤーは、沈黙したままになります。
2. 同じ色の帽子が 2 つあるのを見たプレイヤーは、反対の色を推測します。

3人のプレイヤー全員が同じ色の帽子をかぶっている2つのケースでは、全員が間違った推測をすることになります。しかし、他の6つのケースでは、1人のプレイヤーだけが自分の帽子が他のプレイヤーの帽子と反対色であると正しく推測します。^[25]

• 認識論的論理
• 常識（論理）