uDiary

◆ 100人の囚人パズル

http://sspp2nd.blogspot.com/2008/04/100_29.html (reddit/r/ja 経由)

100人の囚人がいて、100個の木箱の中にそれぞれの名前がかかれている紙が入っています。

100個の木箱はある小部屋に置かれており、囚人は一人ずつその小部屋に連れて行かれ、 100個の木箱のうち50個を開く事が許されます。開いた50個の中に自分の名前があればセーフ。 なければアウトです。囚人は部屋の状態を元通りに戻し、部屋を出ます。 部屋を出た後は他の囚人と連絡を取る事はできませんが、 入る前にみんなで作戦を立てる事はできます。

一人でも開いた50箱の中に自分の名前がなかった者がいれば、全員死刑です。 みんな生き残りたいので、3割以上の確率で生き残れる戦略を考えて下さい。

無策で臨んだ場合の生存確率にくらべると、３割とは異常に高い。 ぐー、ほんとにそんな方法はあるんだろうか？

ぐあぁ、gaz さんのコメント (2008/04/30 13:13:00) をみてしまった！ たしかに、無策でいくよりも、ぐんと生存確率があがりそう。

これで本当に「３割以上」の条件を満たすのかどうかってのは、 群論の問題なんじゃないのかなぁ。任意の置換を、互換の積で表したときに……なんとか、かんとか。

結城さんのところで、「iPod の曲をシャッフルする方法」が取り上げられていたことがあるけど、 あれとも関連しているような……。

あとでやる。

追記

ああ、ダメな子の僕は、ググってしまった！！

http://reddit.com/info/6hi6b/comments/c03vjhr

Seven Puzzles You Think You Must Not Have Heard Correctly with solutionsの解説が詳しめかな。

読んだんだけど、"(k - 1)! ways to order them" のところが腑に落ちない。 いや、サイクル長を変えないためには、末尾を変えちゃいけないってのはわかるんだけど。 （それ以前に、組み合わせの計算を間違ってて頓挫してたのは内緒だ）。