*[[Problem 503:http://projecteuler.net/problem=503]] 「一か八か」 [#t1b05626]
アリスは 1 から '''n''' までの番号が付いた '''n''' 枚のカードを使ってゲームを遊んでいる.
このゲームは以下のようなステップの繰り返しから構成されている.~
(1) アリスはランダムにカードの山から一枚を選ぶ.~
(2) アリスはそのカードの数字を見ないでおく. 代わりに友人のボブがその数字を見て, 今までに見た数字の中で今見ている数字よりも大きいものが何個あるかをアリスに伝える.~
(3) アリスはゲームを終えるか続けることができる. もし終了することを選ぶと, 現在の数字が彼女の点数となる. もし続けることを選ぶと, 選んだカードを捨てて (1) のステップに戻る. カードが残っていなければ, 強制的にゲーム終了となる.
アリスが点数を最小化するよう最適な戦略を取った時の点数の期待値を F('''n''') としよう.
例えば, F(3) = 5/3 となる. 最初のターンでは, アリスはゲームを続けたほうが良い. 次のターンでは, ボブが今見ている数字よりも大きな今までに見た数字が1つあると伝えた時はゲームを終えたほうが良く, そうでなければゲームを続けたほうが良い.
F(4) = 15/8, そして F(10) ≈ 2.5579365079 であることを確かめることができる.
F(10&sup{6};) を求めよ. 回答は小数点以下が10桁となるよう四捨五入して答えよ.
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
