百人の囚人の賭け（解答）

昨日の 「百人の囚人の賭け」 パズルの解答。
まず、囚人たち全員で各人に各名札を割り当てる。 名札に書かれた名前と混乱するので、「担当」という言葉を使おう。 例えば、一列に並んでいる名札に対して、 一番左の名札は囚人Ａの「担当」、次の名札は囚人Ｂの「担当」、 というように各人への名札の割り当てを約束する。 この割り当ては全員で一つ決めさえすれば何でも良い。 各囚人は部屋に入ったらまず自分の「担当の」名札を調べる。 そして、その名札に書いてある名前の囚人の「担当の」名札を調べる。 さらに、その名札に書いてある名前の囚人の「担当の」名札を調べる、 という手順を自分の名前に当たるか、五十個を調べるまで続ける。 これが、答の戦略である。 今、初めてこの答を知った人は、よほど数学的直観に優れた方でない限り、 「はあ？そうしたところで確率はほぼゼロのまま変わらないでしょう？」 と思ったことだろう。その気持ちは良く分かる。 最近の私は老境に至ったせいか、自分の愚かさをフランクに直視できるようになってきたので、 正直に認めてしまうが、私も答を知ってしばらくの間、その意味が分からなかった。 何故、これで囚人全員ともが釈放される確率が 30 パーセント以上にもなるのか？ 以下で、ちょっとくどいくらいに説明してみよう。

数学の言葉で言えば、「ランダム置換のサイクル長の分布の性質による」、 ということなのだが、とりあえず小さな例で具体的に説明する。 数学が得意な方は次の段落を飛ばして下さい。最後の段落に一般的な説明と文献情報があります。

では、囚人が 4 人で、2 回以内に自分の名札をひけば釈放、というケースでやってみよう。 囚人の名前を A, B, C, D とする。 まずは例として、テーブルの名札は左から D, C, B, A の順に並んでいるとしよう。 もちろん、囚人たちはこのことを知らない。 まず名札の担当者を打ち合わせる。左から A, B, C, D と決めたとしよう。 囚人 A は部屋に入ると、自分の担当の名札、つまり一番左の名札を確認する。 その名札には D の名前が書いてあるから、次は D の担当の名札、つまり 4 番目の名札を確認する。 そこには A の名前が書いてあるので「当たり」。 囚人B, C, D についても同様に、全員 2 回で「当たり」をひけることが分かる。 では、別の例でやってみる。 名札が B, C, D, A と並んでいるとしよう。今回は、 囚人 A は 1 番目の名札を調べ、2 番目の名札を調べ、3 番目の名札を調べ、ようやく最後の 4 番目で自分の名札に当たる。 残りの囚人たちも同じく、自分の名札に行き着くのに 4 回かかってしまう。 この二つの場合の違いは何だろうか。 それは、自分の担当の名札から始まって、そこに戻ってくるまでの「輪」の長さである。 一つ目の例では、A と D の輪、B と C の輪になっていて、長さ 2 の輪が二つある。 一方、二つ目の例では、A, B, C, D が輪になっていて、長さ 4 の輪が一つある。 これが違いだ。 ポイントはこの輪の長さが短いケースがけっこう多いことである。 実際、数学的事実として、全ての輪が全体の長さの半分以下であるケースが30パーセントを越す。 この 4 つの名札の場合で考えてみると、名札の並べ方は全部で 24 通りあるが、 そのうちで、長さ 2 以下の輪しか含まない並べ方が 10 通りある。 確率で言えば、そのような並べ方にあたる確率は 10/24 であって、これはもちろん 30 パーセントより大きい。

ここでこの問題の本質をまとめれば、こういうことだろう。 囚人たちは、並び換えの中の「輪」という隠された構造に注目することで、 名札の並びの「美味しいところ」を調べることができ、 しかも、 内在的な性質を用いているが故に、それを指し示すだけで、つまり、 事前に了解しあっておくだけで、そのことが可能なのである。

では、数学が得意な方向けの説明。 結局、100 個の要素の置換に対して、自分の名前を含む巡回(サイクル)の長さが、 50 以下ならば「当たり」ということになるので、 その置換の中にある巡回の長さが全て 50 以下ならば全員が釈放される。 2n 要素の置換の中にある長さ k のサイクルの個数を数えることは、 組合せ論の易しいエクセサイズに過ぎない。ランダムな置換に対して、 長さが丁度 k (> n) のサイクルを含む確率が 1/k であることが分かるので、 囚人全員が「当たり」を引く確率は、 1 から 1/51 + 1/52 + ... + 1/100 を引いたものになり、31.18 パーセントを越える。 さらに言えば、囚人の数が無限大の極限では 1 - log 2 になる。 数学的な興味としては、この戦略は最善なのか、という疑問が当然浮かぶが、 その答はイエスであることが次の最近の論文で証明されている。 E.Curtin and M.Warshauer: "The Locker Puzzle", The Math. Intelligencer 28:1, 28--31 (2006). なお、最初にこのパズルの概念が現れたのは、情報科学系の論文 A.Gal and P.B.Mitersen: "The Cell Probe Complexity of Succinct Data Structures", Lec.Note in Comp.Sci 2719, Springer, 332--344 (2003)で、 著者たちも執筆時点ではこのような戦略があるとは思っていなかったそうだ。 以上の文献情報は、"Mathematical Mind-Benders" (P.Winkler 著/ AK Peters, Ltd.)で知った。

さらに註(28 Apr. 2012):
読者の方から指摘があり、 最後の段落で、「少なくとも一つ長さが丁度 k のサイクルを含む確率が 1/k」とおかしなことを書いていたのを訂正。 正しくは、k が置換の長さの半分より大きいとき、長さが丁度 k のサイクルを含む確率が 1/k。 k が全体の半分より長いのが味噌で、数えるのが易しい。 全体の長さを 2n とすると、長さ k のサイクルの要素を選ぶ方法が 2n 個から k 個選ぶ組合せの数 (2n)!/((2n - k)!k!) だけあり、 その要素の並び換えが (k - 1)! 通りあり、選ばなかった要素の並び換えが (2n - k)! 通りあるから、 長さ k のサイクルを含む置換はこれらの積をとって (2n)!/k 通りある。 置換の方法は全部で (2n)! 通りあるから、これらを一様として、求める確率は 1/k。