Project Euler Problem 499

Solution

Answer: 0.8660312

Let

$m$ = cost per game,
$S_n$ = gambler’s fortune after $n$ games,
$X$ = net gain from one game.

A game ends after $k\ge 0$ heads followed by a tail, so:

$$P(X = 2^k - m)=2^{-(k+1)}.$$

The gambler survives forever iff the fortune never drops below $m$.

We must compute $p_{15}(10^9)$.

1. Mathematical analysis

Define the ruin probability

$$q_m(s)=1-p_m(s),$$

the probability that the gambler eventually runs out of money.

For $s<m$,

$$q_m(s)=1.$$

For $s\ge m$, conditioning on the first game gives

$$q_m(s) = \sum_{k=0}^{\infty} 2^{-(k+1)} q_m(s-m+2^k).$$

We look for an exponential solution

$$q_m(s)=r^{,s-m+1} \qquad (0<r<1).$$

Substituting:

$$r^{s-m+1} = \sum_{k=0}^{\infty} 2^{-(k+1)} r^{s-m+1-m+2^k}.$$

Cancel the common factor $r^{s-m+1}$:

$$1 = r^{-m} \sum_{k=0}^{\infty} 2^{-(k+1)}r^{2^k}.$$

Equivalently,

$$r^m = \sum_{k=0}^{\infty} \frac{r^{2^k}}{2^{k+1}}.$$

This has a unique root $r\in(0,1)$.

The recurrence and boundary conditions determine the solution uniquely, giving

$$q_m(s)=r^{s-m+1},$$

hence

$$p_m(s)=1-r^{s-m+1}.$$

Sanity check against examples

For $m=2$, solving

$$r^2=\sum_{k\ge0}\frac{r^{2^k}}{2^{k+1}}$$

gives

$$r\approx 0.74779150275.$$

Then:

$$p_2(2)=1-r\approx 0.2522,$$

$$p_2(5)=1-r^4\approx 0.6873,$$

matching the problem statement.

For $m=6$,

$$p_6(10000)\approx 0.9952,$$

again matching the given value.

2. Python implementation

import mpmath as mp

mp.mp.dps = 50  # high precision

def survival_probability(m, s):
    # Equation:
    # r^m = sum_{k>=0} r^(2^k) / 2^(k+1)
    def equation(r):
        total = mp.nsum(
            lambda k: r ** (2 ** k) / (2 ** (k + 1)),
            [0, mp.inf]
        )
        return total - r ** m

    # Root in (0, 1)
    r = mp.findroot(
        equation,
        (mp.mpf('0.99999999'),
         mp.mpf('0.999999999'))
    )

    # p_m(s) = 1 - r^(s-m+1)
    return 1 - r ** (s - m + 1)

ans = survival_probability(15, 10**9)

print(ans)
print(f"{ans:.7f}")

3. Code walkthrough

Root equation

def equation(r):

Defines

$$\sum_{k\ge0}\frac{r^{2^k}}{2^{k+1}} - r^m.$$

The infinite sum converges extremely quickly because $2^k$ grows exponentially.

Finding the root

r = mp.findroot(...)

For $m=15$, the root is very close to $1$, so we start with guesses near $1$.

We obtain:

$$r \approx 0.999999997989851406468805941\ldots$$

Final probability

Using

$$p_{15}(10^9) = 1-r^{10^9-14},$$

gives

$$p_{15}(10^9) \approx 0.866031230202843659\ldots$$

Rounded to 7 decimal places:

$$0.8660312$$

4. Final verification

Probability is in $[0,1]$: ✔️
Very large initial fortune ($10^9$) with positive expected growth suggests high survival probability: ✔️
Result (~86.6%) is plausible since for $m=6$, $s=10000$ survival is already ~99.5%, but $m=15$ is significantly harsher: ✔️
Sample cases reproduce exactly: ✔️

Answer: 0.8660312