飛廉さんから聞いた問題。
囚人が 100 人います。ある部屋に 100 個の箱があり、囚人の名札が 1 枚ずつランダムに入っています。
これから囚人が 1 人ずつ部屋に入り、自分の名前を探します。
- 1 人あたり 50 個の箱をあけます。
- その中に自分の名前がなければ、全員処刑されます。
- 事前に相談することはできますが、誰かが部屋に入ったら一切の情報交換が禁止されます。
- 次の人が部屋に入るとき、部屋や箱の状態は完全に初期化されます。
100 人全員が助かる方法を 30% 以上にする方法を答えなさい。
とてもおもしろかった。絶妙。問題を作った人はすごい。
ちなみに、100 人でなくても任意の n 人でいけます。
補足: 箱は識別可能です。1 から 100 のラベルが貼ってあると思ってください。「完全に初期化されます」は「完全に初期状態に戻ります」と思ってください。
