Project Euler 267

题目

Billionaire

You are given a unique investment opportunity.

Starting with \(£1\) of capital, you can choose a fixed proportion, \(f\), of your capital to bet on a fair coin toss repeatedly for \(1000\) tosses.

Your return is double your bet for heads and you lose your bet for tails.

For example, if \(f=\dfrac{1}{4}\), for the first toss you bet \(£0.25\), and if heads comes up you win \(£0.5\) and so then have \(£1.5\). You then bet \(£0.375\) and if the second toss is tails, you have \(£1.125\).

Choosing \(f\) to maximize your chances of having at least \(£1,000,000,000\) after \(1,000\) flips, what is the chance that you become a billionaire?

All computations are assumed to be exact (no rounding), but give your answer rounded to \(12\) digits behind the decimal point in the form 0.abcdefghijkl.

解决方案

令\(N=1000,M=10^9\).根据题意，选定了\(f\)后抛一次硬币，如果正面向上，那么资本变成原来的\((1+2f)\)倍，否则变成原来的\((1-f)\)倍。

那么，如果在整个过程中有\(n\)次硬币正面在上，那么最终获得的金额数是：

\[P(n)=(1+2f)^n\cdot(1-f)^{N-n}\]

不难发现，随着\(n\)增长，\(P(n)\)也在增长，那么存在一个最小的\(n=n_0\)使得\(P(n_0)\ge M\)。因此题目就转化成：求值\(f\)，使得这个\(n_0\)能够最小。

对不等式两边取对数，可以写成：\(n\log(1+2f)+(N-n)\log(1-f)\ge \log M\)

经过移项，那么可以写成\(n(\log(1+2f)-\log(1-f))+N\log(1-f)\ge \log M\)

由于\(f>0\)，因此移项后就写成\(n\ge\dfrac{\log M-N\log(1-f)}{\log(1+2f)-\log(1-f)}\)

令函数\(h(x)=\dfrac{\log M-N\log(1-x)}{\log(1+2x)-\log(1-x)},0< x<1\).那么此时就是为了求函数\(h(x)\)的最小值。这里使用scipy.optimize中的fminbound方法求函数\(h\)的极小值点\(x_0\)。

那么，最小的\(n_0\)就满足\(n_0=\lceil h(x_0)\rceil\)。

根据二项分布的性质，不难得出最终结果为\(\dfrac{\sum_{i=n_0}^N\binom{N}{i}}{2^N}\).

代码

from math import log2, ceil
from scipy.optimize import fminbound
from tools import get_pascals_triangle

N = 1000
M = 10 ** 9
h = lambda x: (log2(M) - N * log2(1 - x)) / (log2(1 + 2 * x) - log2(1 - x))
f = fminbound(h, 0, 1)
n0 = ceil(h(f))
C = get_pascals_triangle(N)
ans = sum(C[N][j] for j in range(n0, N + 1)) / (1 << N)
print("{:.12f}".format(ans))