読者です 読者をやめる 読者になる 読者になる

Redundanz

僕の言葉は、人と話をするためにあるんじゃない。

100人の囚人と50個の箱問題

puzzle

3日くらい考えていた問題が解けたので書いておきます。

100人の囚人がいます。
事前に作戦を相談することができますが、ゲームが始まると互いにコミュニケーションは取れません。
各囚人には固有の名前が付けられています(1から100までの番号でいいでしょう)。

看守が部屋に1から100までの番号がついた100個の箱を用意し、それぞれの箱には囚人の名前が書かれた紙が1枚ずつ入っています。
それぞれの箱には囚人一人の名前が入っていて、また囚人のそれぞれの名前はただ一つの箱に入っています。つまり囚人の名前と箱は1対1に対応しています。トリックはありません。
看守は無作為に囚人の名前を箱に配分しています。

囚人たちは一人ずつ部屋に入ります。ゲーム中には互いにコミュニケーションが取れないので、順番はわかりません。部屋に入ると100個の箱のうち、50個の箱を開けて中を確認します。そして紙に書かれた名前を見て、箱をすべて閉じて最初の状態に戻し、部屋を出ていきます。

すべての囚人が50個の箱のどれかに自分の名前を見つけることができれば、囚人たちは釈放されます。しかし一人でも自分の名前が見つけられなければ、他の囚人の論理パズルでもありがちな設定の通り、囚人たちは処刑されます。

そこで、囚人たちが生き残る確率が高くなるように、30%以上の確率で生き残れる作戦を見つけてください。(問題終わり)


どうしたものかと結構悩んだのですけど、ようやく答えをひらめきました。
ええと、囚人は自分の番号と同じ箱を開けて、出てきた名前が自分のものでなければ、その名前の人の番号に対応する箱を開ける、ということを繰り返せばよいのです。50回の制限がなければ、必ずこの連鎖はループして自分の名前の入った箱で終わります。ですから後は、全てのループが50回以内で終わる確率が30パーセント以上であることを示せばよいことになります。

n個(n>=51)のループがひとつある確率p_n
\displaystyle{p_n = \frac{_{100} C _n \times (n-1)! \times (100-n)!}{100!} = \frac{1}{n} }
よって求める確率は
\displaystyle{1 - \sum_{i=51}^{100} p_n= 1 - ( \frac{1}{51}+\frac{1}{52}+\frac{1}{53} \dots \frac{1}{100}) \approx 0.3118278206898048}

というわけで30パーセント以上の確率で釈放されます。