PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 121 / 円盤ゲームの賞金額

袋の中に赤い円盤 1 枚と青い円盤 1 枚が入っている。賭けゲームにおいてプレイヤーは円盤を 1 枚ランダムに取り出し,その色を記録する。各ターンの終わりに円盤は袋に戻され,追加の赤い円盤 1 枚が袋に足され,次の円盤がランダムに取り出される。

プレイヤーはゲームをプレイするのに 1 ポンドを支払い,ゲーム終了時に青い円盤を赤い円盤より多く取り出していれば勝利する。

ゲームが 4 ターンプレイされたとすると,プレイヤーが勝利する確率は 11/120 となる。したがって,胴元が赤字の見込みになるまでにこのゲームで勝ちに対して割り当てるべき賞金の最大は 10 ポンドとなるであろう。支払いはすべてポンドの整数倍であり,またゲームをプレイするのに支払われたもともとの 1 ポンドを含んでいるため,与えられた例では実際にはプレイヤーは 9 ポンドを獲得することに注意しよう。

15 ターンのゲーム 1 回に割り当てられるべき賞金の最大値を求めよ。

Problem 121 - Project Euler


賞金の決め方がよくわかりませんが,120/11=10.90... なので,プレイヤーが勝つ確率を P として 1/P の整数部分を求めればいいのでしょう。

これは確率の漸化式の問題です。n 回の時点で青を k 回出している確率を P(n, k) とします。

  • n-1 回の時点で k-1 回出していて,n 回目は青
  • n-1 回の時点で k 回出していて,n 回目は赤

袋の中の円盤が毎回1枚ずつ増えることに注意して漸化式を立てます。

 P(n, k) = \dfrac{1}{n + 1}P(n - 1, k - 1) + \dfrac{n}{n + 1} P(n - 1, k)

P(15, 8)〜P(15, 15) の和の逆数の整数部分をとれば終わりです。

プレイヤーが勝つ確率はかなり汚い数です。手計算ではとてもやりたくない……