当サイトを閲覧いただきありがとうございます。 本記事は現代論理クイズの最高傑作と名高い「100人の囚人問題」について解説します。
100人の囚人に1から100の番号が振られ、別室には100個の箱が並んでいます。箱の中には1〜100の番号札が1枚ずつ、でたらめな順番で入っています。囚人は1人ずつ入室し、最大50個まで箱を開けて、自分の番号札を見つけなければなりません。1人でも失敗すれば全員処刑。入室後の連絡や、開けた箱を動かすことは一切できません。全員がでたらめに開けると生存率は2分の1の100乗、小数点以下に0が30個並ぶ絶望的な確率です。ところが、ある開け方をするだけで生存率は約31%まで跳ね上がります。
100人の囚人問題とは
100人の囚人問題（英語では 100 prisoners problem）とは、個々の成功確率を上げられないのに、チーム全体の成功確率だけを劇的に上げられるという、にわかには信じがたい構造を持つ確率パズルです。ルールを整理しておきます。
・囚人は100人。それぞれに1〜100の番号が振られている ・別室に100個の箱が並び、中には1〜100の番号札がランダムに1枚ずつ入っている ・囚人は1人ずつ入室し、最大50個まで箱を開けられる。自分の番号札を見つけたら成功 ・開けた箱は元通りに閉じる。部屋の中の物を動かしたり、印を残したりはできない ・先に入った囚人と後の囚人は、一切連絡を取れない。作戦会議は入室前に1回だけ ・100人全員が成功したときだけ、全員が釈放される
各囚人は100箱のうち50箱しか開けられないので、どう工夫しても1人あたりの成功確率は50%を超えられません。それが100人分掛け合わさるのだから、生存率は事実上ゼロ。ここまでは誰でもたどり着く結論で、だからこそこの問題の答えは衝撃的です。
2003年に生まれた最年少の古典
このパズルの歴史は論理クイズとしては異例なほど新しく、出典もはっきりしています。2003年、デンマークの計算機科学者ペーター・ブロ・ミルターセンがアンナ・ガールとの共著論文の中で原型を提示しました。もともとはデータ構造の限界を調べる理論計算機科学の研究から生まれた問題です。
面白いのは、ミルターセン自身も当初は「良い戦略はない」と考えていたと伝えられていることです。のちに同僚のスヴェン・スキュームが見つけた戦略は、専門家の予想を裏切る鮮やかさで、2006年には数学者カーティンとウォーシャウアーによってこれ以上良い戦略が存在しない（最適である）ことの証明まで与えられました。
その後このパズルは数学パズル界の新定番となり、2022年に人気の科学系動画チャンネルが取り上げたことで、一般にも爆発的に広まりました。生まれてから20年ほどで「現代の古典」の座に就いた、珍しい問題だと思います。
答えは「自分の番号の箱から数字をたどる」
作戦は拍子抜けするほど単純です。
まず自分の番号と同じ番号の箱を開ける。中の札に書かれた番号の箱を次に開ける。その中の札の番号の箱をまた開ける。これを50回繰り返す。
たとえば囚人28番なら、まず箱28を開けます。中に札52が入っていたら、次は箱52。そこに札7があれば、次は箱7。札の数字が次に開ける箱を指定するという、それだけの規則です。
一見するとでたらめに開けるのと変わらないように思えます。しかしこの開け方には、決定的な性質が隠れています。箱と札の対応をたどっていくと、必ずいつかは出発点である自分の番号の札にたどり着くのです。箱28から出発した旅は、箱の中に札28を見つけた瞬間に終わります。つまり道に迷うことは絶対にない。問題はただ一つ、その旅が50歩以内に終わるかどうかだけです。
生存率31%を生み出すサイクルの数学
箱と札の対応は、数学で言う「置換」です。そして置換は必ず、いくつかの輪（サイクル）に分解できます。箱28→箱52→箱7→箱28と戻ってくるなら、この3つの箱は長さ3の輪を作っています。100個の箱の世界は、こうした輪の集まりに過不足なく分かれています。
囚人がたどる旅は、自分の番号が属する輪をぐるりと一周することに他なりません。輪の長さが50以下なら、その輪に属する囚人は全員50歩以内に自分の札へたどり着きます。逆に長さ51以上の輪が1つでもあれば、その輪の囚人たちは全員失敗します。
つまり全員の運命は、たった一つの問いに集約されます。「ランダムな置換に、長さ51以上の輪はあるか？」
長さ51以上の輪は、あるとしても1つしか存在できません（51+51は100を超えるからです）。長さちょうどkの大きな輪ができる確率は「kぶんの1」であることが計算でき、失敗確率は51ぶんの1から100ぶんの1までの和で約69%。したがって成功確率は約31%になります。囚人の数を増やしていっても、この値は約30.7%までしか下がりません。100人だろうと100万人だろうと、3割前後の生存率が保たれるのです。
小さな例で確かめてみます。囚人4人・箱4個・開けられるのは2箱の場合、失敗するのは長さ3の輪ができるとき（確率3ぶんの1）か、長さ4の輪ができるとき（確率4ぶんの1）です。合わせて12ぶんの7なので、成功確率は12ぶんの5、約42%。でたらめに開けた場合の全員成功は16ぶんの1（約6%）ですから、たった4人の世界でも作戦の威力ははっきり現れます。
個人の運命は変わらず、運命の重なり方だけが変わる
ここで、冒頭の「1人あたり50%の壁」を思い出してください。実はサイクル戦略を使っても、個々の囚人の成功確率はきっかり50%のままです。自分の属する輪の長さが50以下である確率は、計算するとちょうど2分の1になります。壁は1ミリも破られていません。
では何が変わったのか。成功と失敗の重なり方です。でたらめ戦略では100人の運命がバラバラの独立事象なので、全員成功はほぼ起こりえません。サイクル戦略では、同じ輪の囚人は全員成功するか全員失敗するかのどちらかになり、100人の運命が数本の輪に束ねられます。長い輪がなければ全員助かり、あれば大勢が一緒に沈む。失敗を全滅の側に寄せ集め、成功を「全員生還」に固めることで、全員成功の確率だけが跳ね上がるわけです。
当シリーズの帽子のパズルで紹介したエバートの帽子ゲームと、原理はまったく同じです。「個人の勝率は変えられなくても、勝ち負けの相関は設計できる」この発想は、保険が多数の契約者のリスクを束ねて成り立つ仕組みや、ポートフォリオで資産の連動性を調整する発想にもつながる、確率の世界の奥義だと思います。
なぜ自分の番号の箱から始めるのか
出発点を自分の番号にすると、たどっている輪の終点が必ず自分の札になるからです。箱をたどる旅は輪を一周して出発点に戻る直前、つまり「札に出発点の番号が書かれている箱」で終わります。出発点が自分の番号なら、その最後の札こそ探している自分の札です。適当な箱から出発すると、自分の札を含まない輪を延々と回ってしまう可能性があり、この保証が消えてしまいます。
看守が札の配置を意地悪に決めたらどうなりますか？
鋭い指摘で、この戦略が有名になった今、看守がわざと長さ51以上の輪を作れば全滅します。しかし対策があります。囚人たちが事前に「箱の番号の読み替え表」を1つ共有しておき、全員がその読み替えを通してたどればよいのです。看守の配置に囚人側のランダムな置換を重ねると、結果はまたランダムな置換になり、約31%が復活します。相手の悪意を自分側の乱数で洗い流すという、暗号理論でも使われる考え方です。
開けられる箱が50個ではなく60個や30個ならどうなりますか？
成功確率は「長さがその数を超える輪がない確率」に変わります。60個なら約49%、70個なら約64%まで上がります。逆に開けられる数が半分を下回ると、長い輪が同時に複数できるようになって計算は複雑になり、成功率は一気に落ち込みます。半分の50個という設定は、絶望的に見えて実は3割も助かるという、驚きが最大になる絶妙な調整だと言えます。ちなみにでたらめ戦略の場合、60個開けられても全員成功の確率は0.6の100乗でやはり事実上ゼロです。
関連する論理クイズ・パズル
「勝敗の重なり方を設計する」原理が共通する「帽子のパズル」、同じく確率と戦略で勝率を最大化する「秘書問題」、確率の直感が崩壊する定番「モンティ・ホール問題」の記事です。
まとめ
本記事は「100人の囚人問題」について解説しました。如何だったでしょうか。
50%の壁は誰にも破れないのに、全員生還の確率はほぼ0%から31%へ跳ね上がる。種明かしを聞いても狐につままれたような感覚が残るのは、私たちが確率を個人単位でしか考えない癖を持っているからだと思います。このパズルが教えてくれるのは、確率には「大きさ」だけでなく「重なり方」という設計の余地があるということです。
自分の番号の箱から、札の数字をたどる。この単純な規則が100人の運命を数本の輪に束ね直す様子は、何度考えても見事という他ありません。私は初めて答えを知ったとき、本当に成り立つのかとしばらく疑ってしまいました。この疑いを小さな例で自力で潰していく過程まで含めて面白い問題なので、是非4人版あたりから試してみてください。
論理クイズ・確率パズルの一覧に戻りたい方は以下のリンクからどうぞ。
それでは次の記事も閲覧いただけると幸いです。
📚 シリーズ：論理クイズ・確率パズル（10/11）
