99人の囚人がいます.
彼らの背中に1~100までのナンバーが書かれたゼッケンをランダムに割り当てます.
彼らは他人のゼッケンは見ることができても,自分のゼッケンは見ることができません.
ゼッケンの数は全部で100なので,一枚使われずに余りますが,その余ったナンバーは囚人達にはわからないようにしておきます.
この状況で,囚人たちに一斉に自分のナンバーを宣言させて,全員が正解だったら釈放するという賭けをします.
囚人たちにはゼッケンをつけられる前に相談タイムが設けられていますが,ゼッケンをつけた後は一切相談することはできません.
どういう戦略を取れば,助かる確率を最も高くできるでしょうか?
この問題が面白かった.
確率は1/2にできる.
全員正解するか,全員ことごとく(一人残らず)外れるか,のどちらかにできる.
そう,置換ならね.
囚人の戦略は次の通り.
予め,囚人らは点呼を取っておく.囚人1,囚人2,…囚人99,というふうに順番付けをしておく.
そして次に.100番目の1つ余ったナンバーは架空囚人100のナンバーであるという風に取り決めをしておく.
最後に,たとえば偶置換(あるいは奇置換のどちらか)に賭けることを約束しておく.(もちろん囚人全員に置換の特別講義が必要であるが…)
これだけである.
いざ,ゼッケンが配られると,囚人は自分のゼッケンのナンバーは分からないので,
98個のナンバーを把握し,残り2個のナンバーのうちどちらかが自分のナンバーで,どちらかが余りのナンバーであることを悟る.
そこで,一旦全員で点呼を取る.
囚人らは,囚人1,囚人2,…囚人99と並ぶ.彼らには(当然その点呼の数字とは無関係に)ゼッケンのナンバーを有している.
たとえば,囚人1は5, 囚人23は71 といった具合である.
ここで,囚人1の立場になって考えてみよう.
囚人1は自分のナンバーを知らない.それと同時に,100番目の1つ余ったナンバー(架空囚人100のナンバー)も知らない.
これらの2つの数字のどちらかが自分で,どちらかが囚人100のナンバーである.
それらを入れ替えて得られる場合も考慮すれば,囚人1の頭の中には2通りの可能性が考えられる.
しかし,ここで約束通りに偶置換になる(= 適当な二人を入れ替える操作を偶数回行なって,ゼッケンの数字を点呼順にする)場合の方を採用したなら,この可能性は必ず2つのうち1つに絞られる.
これを99人の囚人全員が実行すれば,囚人は「全員正解」または「全員不正解」の確率50%づつになる.