「夫子憮然曰、鳥獣不可與同羣。吾非斯人之徒與、而誰與。
「論語」微子、第十八、六

2012/04/23

百人の囚人の賭け(出題)

今日のパズルは難しい。 問題も答も易しいが、なぜそれが答なのかを理解するのにかなり深い数学を必要とする。 しかし、非常に不思議な、衝撃的なパズルなので紹介してみる。 私自身はこのパズルを数年前、K 大の S 井君から教わった。 ある研究会のあとの懇親会で、会場に移動する道すがら出題され、 私はその懇親会のあいだ、パーティそっちのけで真剣に考えた末、 「絶対に答はありえない」としか思えなかった。 また、S 井君自身も何日か考えたが分からない、と言っていた。 しかし、「S 田さんは解けたらしいので、問題は間違っていないし、答があるはず」 とのことだった。 S 井君と S 田さんの二人は確率論のプロであると同時に、 私の知る人の中で屈指の頭脳の持ち主である。 その二名でも一勝一敗だったほど、このパズルは難しい。 私も入れれば一勝二敗だが、それはどうでもいいね。

無期懲役の百人の囚人に対し、恩赦の賭けが提供されることになった。 部屋の中のテーブルに、この百人の名札が裏を向けて横一列に並べられている。 囚人は一人ずつこの部屋に入り、 百個の名札のうち五十個まで自分の好きに選んでは表に返して名前を確認できる。 この五十個のうちに自分の名札があれば「当たり」で、その囚人は釈放される。 「当たり」でもそうでなくても、囚人は名札を元通りに裏返して別の出口から部屋を立ち去り、 そののち、次の囚人が入室する。 よって、囚人の間で連絡する手段はないし、何か状況を変えたり、情報を残す方法もない。 各囚人が自分の名札を見つける確率は 50/100、つまり二分の一だから、 百人全員が釈放される確率は公平なコイン投げを百回して百回とも表が出る確率に等しく、 ほぼゼロである。

ここからが本題。今、確率はほぼゼロと言ったばかりだが、 この賭けを始める前に囚人全員で打ち合わせをして良いなら、 百人全員が釈放される確率を 30 パーセント以上にできる戦略がある。 (本当です。嘘じゃないです。) その戦略とはどんなものでしょう? 答はいつものように明日。