2009年04月24日
Twitterで見かけたので取り組んだ問題。
問．「１０人の紳士がバーに来て、傘を傘立てに入れた。帰りにはみんなよっぱらって、でたらめに傘を持って帰った。少なくとも一人の紳士が自分自身の傘を持って帰る確率は？」
漸化式を立てる時点で結構苦戦した。漸化式を手で解くのは困難だったため、最後の計算はプログラムを書いて行った。
（以下回答）
人物を{p1, p2, ... , pn}とし、人物pi (1≦i≦n) のものである傘を ui とする。
人数がn人であるとき、全ての考えられうる傘の取り方は n! 通りである。
また人数がn人であるとき、誰も自身の傘を持ち帰らないような傘の取り方を an とする。
このとき、求める確率は 1 - (an / n!) と表される。
誰も自身の傘を持ち帰らないような傘の取り方 an を求めることを考える。なお n＝1 の場合は除外する（明らかに a1＝0 である）。
まず人物 p1 については、自分の傘を持ち帰らないとすればよい。すなわち p1 の傘の取り方は (n-1) 通りある。
ここで、p1 が傘 ui (i≠1) を取ったとする。このとき、次に pi に傘を持ち帰らせる。ここでこの段階では、pi が ui を持ち帰ることはない（p1が持ち帰っているため）。
もしここで仮に、pi が u1 を持ち帰ったとする。そのような条件を課した場合における、全員が自身の傘を持ち帰らないような持ち帰り方の総数は、「p1 の傘の取り方（(n-1)通り）」×「pi の傘の取り方（1通り）」×「残り(n-2)人による、自身の傘の持ち帰りがない取り方（an-2 通り）」＝ (n-1)an-2 と表される。
しかし実際には、pi がさらに別の傘 uj (j≠1, j≠i)を取るかもしれない。その場合、誰かが u1 を取っていくまで傘を取り続けることが続く。
それを踏まえると、この「傘を取られた人が次に傘を取る」操作が t 人(2≦t≦n)で完結する場合における、条件を満たす傘の取り方は
n-1Pt-1・an-t
と表される（ただし漸化式の内容の整合性のため、a0＝1 と定める）。ここで、n-1Pt-1 が t 人で自身の傘を取らないように傘を取る方法である。
これを踏まえると、求める傘の取り方は以下の式で表される。
an ＝ ��{t=2, 3, ..., n} n-1Pt-1・an-t
すなわち、「a2 を求めるには a0 が必要」「a3 を求めるには a0・a1 が必要」「a4 を求めるには a0・a1・a2 が必要」と言ったような、直前を除いた、添字が小さい全ての値を用いる漸化式となっている。
プログラムを書いて求めるべき確率 1 - (an / n!) を計算すると、以下のような結果になった。ソースコード(Ruby)はこちら
2 guests: 0.5000000000 (1/2) 3 guests: 0.6666666667 (4/6) 4 guests: 0.6250000000 (15/24) 5 guests: 0.6333333333 (76/120) 6 guests: 0.6319444444 (455/720) 7 guests: 0.6321428571 (3186/5040) 8 guests: 0.6321180556 (25487/40320) 9 guests: 0.6321208113 (229384/362880) 10 guests: 0.6321205357 (2293839/3628800) 11 guests: 0.6321205608 (25232230/39916800) 12 guests: 0.6321205587 (302786759/479001600) 13 guests: 0.6321205588 (3936227868/6227020800) 14 guests: 0.6321205588 (55107190151/87178291200) 15 guests: 0.6321205588 (826607852266/1307674368000)どうやら、人数を増やすと0でも1でもない値に収束しそうな感じである。
