Solution

Answer: 2269

Let the game last for $n=15$ turns.

On turn $k$ (starting from $k=1$):

before drawing, the bag contains $1$ blue disc and $k$ red discs,
so the probability of drawing blue is

$$\frac{1}{k+1},$$

and the probability of drawing red is

$$\frac{k}{k+1}.$$

The player wins if the number of blue draws is strictly greater than the number of red draws.

For $15$ turns, that means obtaining at least $8$ blue discs.

Mathematical analysis

Define:

$B_k$: drawing blue on turn $k$,
$R_k$: drawing red on turn $k$.

The probability of a specific sequence of outcomes is the product of the probabilities for each turn.

A key simplification comes from factoring out the common denominator:

$$\prod_{k=1}^{15} (k+1)=16!.$$

Indeed, every outcome probability has denominator $16!$.

If a set $S\subseteq{1,\dots,15}$ represents the turns on which blue is drawn, then:

blue contributes numerator $1$,
red on turn $k$ contributes numerator $k$.

Hence:

$$P(S)=\frac{\prod_{k\notin S} k}{16!}.$$

Since

$$\prod_{k=1}^{15} k = 15!,$$

we can rewrite:

$$P(S)=\frac{15!}{16!\prod_{k\in S}k} =\frac{1}{16\prod_{k\in S}k}.$$

The total winning probability is therefore

$$P(\text{win}) = \sum_{\substack{S\subseteq{1,\dots,15}\ |S|\ge 8}} \frac{1}{16\prod_{k\in S}k}.$$

However, it is computationally easier to compute this with dynamic programming.

Prize fund condition

Suppose the banker allocates a prize fund of $F$ pounds.

The player pays £1 to play.
The payout $F$ includes the returned £1.

Expected payout:

$$F\cdot P(\text{win}).$$

To avoid expected loss:

$$F\cdot P(\text{win}) \le 1.$$

Therefore the maximum allowable integer prize fund is

$$\left\lfloor \frac{1}{P(\text{win})} \right\rfloor.$$

So our task reduces to computing the exact winning probability.

Dynamic programming approach

Let:

$$dp[j]$$

represent the total probability of having exactly $j$ blue draws after processing some turns.

Initially:

$$dp[0]=1.$$

For turn $k$:

blue probability $= \frac1{k+1}$,
red probability $= \frac{k}{k+1}$.

Update backwards:

$$dp[j] = dp[j]\cdot \frac{k}{k+1} + dp[j-1]\cdot \frac1{k+1}.$$

After 15 turns, sum probabilities for $j\ge 8$.

Python implementation

from fractions import Fraction

# Number of turns
N = 15

# dp[j] = probability of getting exactly j blue discs
dp = [Fraction(0, 1) for _ in range(N + 1)]
dp[0] = Fraction(1, 1)

# Process each turn
for k in range(1, N + 1):

    p_blue = Fraction(1, k + 1)
    p_red = Fraction(k, k + 1)

    # Update backwards to avoid overwriting needed values
    for j in range(k, 0, -1):
        dp[j] = dp[j] * p_red + dp[j - 1] * p_blue

    dp[0] *= p_red

# Need strictly more blue than red
# For 15 turns, that means at least 8 blues
win_probability = sum(dp[8:])

# Maximum prize fund
prize_fund = int(Fraction(1, 1) / win_probability)

print(win_probability)
print(prize_fund)

Code walkthrough

Imports

from fractions import Fraction

We use exact rational arithmetic so there is no floating-point error.

DP initialization

dp = [Fraction(0, 1) for _ in range(N + 1)]
dp[0] = Fraction(1, 1)

Before any turns:

probability of 0 blue draws is $1$,
all others are $0$.

Processing each turn

for k in range(1, N + 1):

Turn $k$ has:

p_blue = Fraction(1, k + 1)
p_red = Fraction(k, k + 1)

because the bag contains:

1 blue disc,
$k$ red discs.

Transition

for j in range(k, 0, -1):

We iterate backward so previous-state values are preserved.

Transition:

dp[j] = dp[j] * p_red + dp[j - 1] * p_blue

Two ways to end with exactly $j$ blues:

already had $j$, then draw red,
had $j-1$, then draw blue.

Updating zero-blue state

dp[0] *= p_red

The only way to still have zero blues is to keep drawing red.

Winning probability

win_probability = sum(dp[8:])

For 15 turns, winning requires at least 8 blue draws.

Verification with the 4-turn example

For $N=4$, the same code gives:

$$P(\text{win})=\frac{11}{120},$$

matching the problem statement.

Then:

$$\left\lfloor \frac{120}{11} \right\rfloor = 10,$$

also matching the example.

So the method is validated.

Final computation

For $N=15$, the exact winning probability is

$$\frac{9219406943}{20922789888000}.$$

Thus:

$$\left\lfloor \frac{20922789888000}{9219406943} \right\rfloor = 2269.$$

This is reasonable:

the winning probability is about $0.0004406$,
so the reciprocal is around $2269.4$,
hence the largest safe integer payout is $2269$.

Answer: 2269

Project Euler Problem 121