3日くらい考えていた問題が解けたので書いておきます。
100人の囚人がいます。
事前に作戦を相談することができますが、ゲームが始まると互いにコミュニケーションは取れません。
各囚人には固有の名前が付けられています（1から100までの番号でいいでしょう）。看守が部屋に1から100までの番号がついた100個の箱を用意し、それぞれの箱には囚人の名前が書かれた紙が1枚ずつ入っています。
それぞれの箱には囚人一人の名前が入っていて、また囚人のそれぞれの名前はただ一つの箱に入っています。つまり囚人の名前と箱は1対1に対応しています。トリックはありません。
看守は無作為に囚人の名前を箱に配分しています。囚人たちは一人ずつ部屋に入ります。ゲーム中には互いにコミュニケーションが取れないので、順番はわかりません。部屋に入ると100個の箱のうち、50個の箱を開けて中を確認します。そして紙に書かれた名前を見て、箱をすべて閉じて最初の状態に戻し、部屋を出ていきます。
すべての囚人が50個の箱のどれかに自分の名前を見つけることができれば、囚人たちは釈放されます。しかし一人でも自分の名前が見つけられなければ、他の囚人の論理パズルでもありがちな設定の通り、囚人たちは処刑されます。
そこで、囚人たちが生き残る確率が高くなるように、30％以上の確率で生き残れる作戦を見つけてください。（問題終わり）
どうしたものかと結構悩んだのですけど、ようやく答えをひらめきました。
ええと、囚人は自分の番号と同じ箱を開けて、出てきた名前が自分のものでなければ、その名前の人の番号に対応する箱を開ける、ということを繰り返せばよいのです。50回の制限がなければ、必ずこの連鎖はループして自分の名前の入った箱で終わります。ですから後は、全てのループが50回以内で終わる確率が30パーセント以上であることを示せばよいことになります。
n個(n>=51)のループがひとつある確率は
よって求める確率は
というわけで30パーセント以上の確率で釈放されます。
