PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 267 / 億万長者

あなたに変わった投資の機会が与えられる。

£1 の資産からはじめて固定した比率 f を選び, 資産の中でその比率を公正なコイントスに賭け, 1000 回繰り返す。

賭け金は表のときは倍戻り,裏の時は失う。

例えば f=1/4 のとき,最初のトスでは £0.25 賭け,表が出たら £0.5 を勝ち取り,£1.5 の手持ちとなる。次は £0.375 を賭け,トスで裏が出たら £1.125 となる。

1000 回後に 少なくとも £1,000,000,000 を持っている確率が最大になる f を選ぶと, £1,000,000,000 獲得できる確率はいくらか?

すべての計算は丸めなしで行う。答えは小数点以下12桁に四捨五入し,0.abcdefghijkl の形で入力せよ。

Problem 267 - Project Euler


はじめは「表のときは倍戻り」がピンときませんでしたが,何回か実験してみたらわかりました。

  • 表だったら 1+2f 倍,裏だったら 1-f 倍になる
  • 裏表の順番は関係ない

1000回中表が x 回出た場合の資産は

 (1+2f)^x (1-f)^{1000-x}

これが 10^9 以上となる条件は

 x \geqq \dfrac{9 \log 10-1000 \log (1-f)}{\log (2 f+1)-\log (1-f)}

「裏表の順番は関係ない」から題意の確率が最大になるのは x の個数が最大のときです。上式の右辺 g(f) が最小になる f=f1 を求めて,
[f1]+1 ≦ x ≦ 1000
に対する C(1000, x)/2^1000 の和を求めればよいことになります。

問題の性質上,「g(f) が最小になる」は「極値をとる」で十分です。FindRoot で g'(f)=0 を数値的に解いて計算しました。