漸化式で解く

今回は、日経サイエンスの記事からの問題です。

タイトルは、「続・給仕長帽子屋のたくらみ」というもので、
問題と解答(解説)は、それぞれ次のページにあります。

http://www.nikkei-science.com/page/magazine/alice/201506/question.html
http://www.nikkei-science.com/page/magazine/alice/201506/answer.html

この中で、作者(坂井公先生)は、「期待値を求める場合の常套手段」の「期待値の加法性」を用いて求めています。
残念ながら、私は、それを知らなかったので場合分けで求めました。
もちろん、52人の場合を、場合分けで求めるわけはなく、当然、漸化式を作って、n人の場合での場合分けを行ないます。
漸化式で解く場合は、「考え方」がすべてです。よい考え方が思い浮かぶと、簡単に漸化式が作れます。

下に示す3つの漸化式A(n),B(n),C(n)を用いれば、B(51)が求める答えとなります。
一人が座ったあとの状態で、その人のところで、机を開いて直線状にしたと考えましょう。その人は右のナプキンを取ったものとします。

A(n) は、空いた席が連続してn個ある場合で、かつ、どの席も両方のナプキンが残っている場合の犠牲者の期待値とします。
B(n) は、空いた席が連続してn個で、最初の席の左側のナプキンがなくて、それ以外の席は両方のナプキンが残っている場合の犠牲者の期待値とします。
C(n) は、空いた席が連続してn個で、最初の席の左側のナプキンがなくて、最後の席の右側のナプキンがなくて、それ以外の席は両方のナプキンが残っている場合の犠牲者の期待値とします。

まず、n=1,2の場合は、明らか、あるいは、場合分けで考えれば
A(1)=0, A(2)=0
B(1)=0, B(2)=1/4
C(1)=1, C(2)=1
となります。
なお、n=1のときには、すでに一人が座ったあとに1つ席が空いている場合なので、合計2人の場合のことです。n=2のときは、合計3人の場合のことです。

n>=3のときは、次の人がどの席に座るかで場合分けすると、右側と左側の状態をA(k),B(k),C(k), k<nで表わすことができます。それを足し合わせればA(n),B(n),C(n)での漸化式ができます。途中の場合分けの計算はすべて略しますが、結果として、

となります。

あとは、コンピュータを使って、多倍長有理数を扱える言語で、A(n),B(n),C(n)を求めていき、最終的にB(51)を求めます。
perlのbigratを使って求めた結果は次のとおりです。

112060326012094971768287355884653931841812
97185682894552315055599361672425037016807
/17464044598281107886605680776556174847310
52427739679140223698377637888000000000000

およそ、6.4166となります。