Detailed mathematical approach

Problem Summary

The game starts with one blue disc and one red disc in the bag. On turn \(t\), the player draws one disc uniformly at random, notes its color, returns it, and then an extra red disc is added. Therefore the bag contains exactly one blue disc and \(t\) red discs on turn \(t\), so

$P(\text{blue on turn }t)=\frac{1}{t+1},\qquad P(\text{red on turn }t)=\frac{t}{t+1}.$

There are \(15\) turns in total, and the player wins exactly when blue appears more often than red. Since \(15\) is odd, that means at least \(8\) blue draws. If the total prize fund is \(M\) pounds, including the original stake, then the banker does not lose money on average precisely when \(M \cdot P(\text{win}) \le 1\). The task is to compute the largest integer \(M\) satisfying that inequality.

Mathematical Approach

The crucial quantity is not the order of the draws, but how many blue draws have occurred after each turn. That turns the problem into a small distribution update over the possible blue counts.

The right state variable

Let \(B_t\) be the number of blue draws after the first \(t\) turns, and let

$P_t(b)=P(B_t=b).$

Only the values \(0 \le b \le t\) are possible. To end at exactly \(b\) blue draws after turn \(t\), there are only two possibilities:

$P_t(b)=P_{t-1}(b)\cdot \frac{t}{t+1}+P_{t-1}(b-1)\cdot \frac{1}{t+1},$

with base condition \(P_0(0)=1\) and \(P_0(b)=0\) for \(b \ne 0\). The first term means turn \(t\) was red, so the blue count stayed at \(b\). The second term means turn \(t\) was blue, so the previous count had to be \(b-1\).

Clearing denominators gives the exact recurrence used in the integer implementations

After \(t\) turns, every probability \(P_t(b)\) has denominator

$D_t=\prod_{i=1}^{t}(i+1)=(t+1)!.$

Define the scaled quantity

$A_t(b)=D_t\,P_t(b).$

Multiplying the probability recurrence by \(D_t=(t+1)D_{t-1}\) removes every fraction and yields

$A_t(b)=t\,A_{t-1}(b)+A_{t-1}(b-1).$

This is the invariant exploited by the exact integer versions of the solution. The factor \(t\) comes from the \(t\) red discs available on turn \(t\), while the blue branch contributes a factor of \(1\) because there is always exactly one blue disc.

At the end, the winning probability is

$P(\text{win})=\sum_{b=8}^{15} P_{15}(b)=\frac{\sum_{b=8}^{15} A_{15}(b)}{16!}.$

An equivalent polynomial viewpoint

If we collect the scaled values into a polynomial

$F_t(x)=\sum_{b=0}^{t} A_t(b)x^b,$

then the recurrence above becomes

$F_t(x)=(t+x)F_{t-1}(x),\qquad F_0(x)=1,$

so

$F_t(x)=\prod_{i=1}^{t}(i+x).$

The coefficient of \(x^b\) is exactly the scaled numerator for the event “there are \(b\) blue draws after \(t\) turns.” The implementations never need to manipulate this polynomial symbolically, but it explains why the integer recurrence is so clean.

Worked example: four turns

The four-turn case is small enough to inspect by hand. Starting from \(A_0(0)=1\), the recurrence produces:

$ \begin{aligned} t=0 &: [1] \\ t=1 &: [1,1] \\ t=2 &: [2,3,1] \\ t=3 &: [6,11,6,1] \\ t=4 &: [24,50,35,10,1]. \end{aligned} $

These are the coefficients of

$F_4(x)=(1+x)(2+x)(3+x)(4+x).$

After four turns the common denominator is \(D_4=2\cdot3\cdot4\cdot5=120\). A win requires more blue than red, so with four turns the player needs \(3\) or \(4\) blue draws. Therefore

$P(\text{win in 4 turns})=\frac{10+1}{120}=\frac{11}{120}.$

The maximum profitable prize fund is then

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

which is a good sanity check for the recurrence.

Turning the win probability into the prize fund

For the actual problem, \(n=15\). Let

$W=\sum_{b=8}^{15} A_{15}(b).$

Then

$P(\text{win})=\frac{W}{16!}.$

If the prize fund \(M\) includes the returned stake, the banker's expected payout per game is \(M \cdot P(\text{win})\). To avoid an expected loss we need

$M \le \frac{1}{P(\text{win})}=\frac{16!}{W}.$

Hence the required answer is

$\boxed{M_{\max}=\left\lfloor \frac{16!}{W} \right\rfloor.}$

How the Code Works

Building the distribution turn by turn

The implementation keeps a one-dimensional table indexed by the number of blue draws seen so far. Initially only the state “zero blue draws after zero turns” is nonzero. For each new turn, a fresh table is created and every reachable state contributes to two next states: one red transition that keeps the same blue count and one blue transition that increases it by one.

Two exact-arithmetic strategies

The Python implementation stores the probabilities themselves as exact rational numbers, so each transition multiplies by \(t/(t+1)\) or \(1/(t+1)\). The C++ and Java implementations clear the common denominator at every stage and store only the scaled numerators \(A_t(b)\). That is why their update rule uses integer multiplication by \(t\) for the red branch and plain addition for the blue branch.

Extracting the final integer answer

After the fifteenth turn, the implementation sums all states with more blue draws than red draws, namely \(b=8,9,\dots,15\). In the rational version that sum is already the exact winning probability. In the scaled-integer versions, that sum is the numerator \(W\), while the common denominator is \(16!\). The final answer is obtained by one exact integer division, \(\left\lfloor 16!/W \right\rfloor\).

Complexity Analysis

For \(n\) turns, the table has size \(n+1\), and turn \(t\) processes only the states \(0,1,\dots,t\). The total number of state updates is therefore

$1+2+\cdots+n = O(n^2).$

The memory usage is \(O(n)\), because only the current row and the next row are needed at any time. In this problem \(n=15\), so the computation is tiny. Even with exact fractions or big integers, the numbers remain small enough that arithmetic cost is negligible compared with the simplicity gained from keeping the calculation exact.

Footnotes and References

1. Problem page: Project Euler 121
2. Poisson binomial distribution: Wikipedia - Poisson binomial distribution
3. Probability-generating function: Wikipedia - Probability-generating function
4. Dynamic programming: Wikipedia - Dynamic programming
5. Expected value: Wikipedia - Expected value