Names in Boxes - blanket log

100人の囚人パズルの正解戦略の確率を計算してみました。
ネタバレ含むので自分で考えたい人は見ないでください。

箱の中身を次の箱へのポインタとみなして連結リストを考えます。全てのリストは必ずループとなり、また一つの箱が二つ以上から参照されることはありません。ループが数字の6みたいな形になることはなく、必ず閉じた輪になるということです。
長さmのループを順にたどれば必ずm回で元の箱に戻ってくる（＝自分の名前を引き当てる）ことができます。つまり全員が生き残るには長さ51以上のループが含まれないことが条件です。

n個の箱の中で、長さm以上のループができる確率pは次のようになります。
$p = \frac{ \sum_{k=m}^{n} c(k) \cdot (n-k)! }{ n! }$
分母はn個の名前の配置の並べ替えの総数。
分子は長さ k∈[m..n] のループを持つ場合の数の和で、各項は
「長さ k のループの取り方の数 c(k)」×「最長ループに含まれない箱(n-k)個の並べ方の数」です。
c(k)は具体的には
$c(k) = \frac{\quad_{n}\mathrm{P}_{k}}{k} = \frac{n!}{k(n-k)!}$
となります。(kで割る = ループなのでどこが先頭かを区別しない)

これを p に代入してやると
$p = \sum_{k=m}^{n} \frac{ c(k) \cdot (n-k)! }{ n! } \quad=\quad \sum_{k=m}^{n} \frac{n!}{k(n-k)!} \frac{(n-k)!}{n!} \quad=\quad \sum_{k=m}^{n} \frac{1}{k} \quad=\quad H_{n} - H_{m-1}$
と、調和数が出てきます。

n=100, m=51 で実際計算してみると、p = 0.688 となり、1-p = 0.312 で確かに30％を超える確率で全員助かることがわかります。おもしろいですね。

import Data.Ratio

main :: IO ()
main = do
  let p = fromRational $ sum [ 1%k | k <- [51..100] ]
  print p
  print (1 - p)

{-
0.6881721793101953
0.31182782068980475
-}