Detailed mathematical approach

Problem Summary

A player starts with wealth \(1\) and may bet through \(N=1000\) independent rounds. Each round is won with probability \(p=0.6\), and the goal is to finish with wealth at least \(T=10^{12}\). Because the bets are priced fairly at each step, the right way to analyze the problem is not to enumerate betting rules directly, but to study which terminal states are worth buying under a fixed pricing budget.

The implementations therefore reduce the gambling problem to an optimization problem between two probability measures: the true measure \(P\), where wins occur with probability \(0.6\), and a fair reference measure \(Q\), where each branch has probability \(1/2\). The answer is the largest \(P\)-probability of a success set whose \(Q\)-cost does not exceed \(1/T\).

Mathematical Approach

Let \(\omega\) denote a complete win-loss path of length \(N\), and let \(X(\omega)\) be the terminal wealth delivered on that path. The complete binomial tree lets us price terminal payoffs path by path, so the whole problem becomes a measure-theoretic budget allocation problem.

Step 1: Convert the betting problem into terminal-state payoffs

Under fair even-money pricing, each one-step branch has price \(1/2\). Therefore every full path \(\omega\) has fair price

$Q(\{\omega\}) = 2^{-N}.$

By linearity, any nonnegative terminal payoff \(X\) has initial cost

$\text{cost}(X) = E_Q[X].$

Since the player starts with capital \(1\), every feasible strategy must satisfy

$E_Q[X] \le 1.$

This is the key structural simplification: the space of adaptive betting strategies can be replaced by the space of terminal payoffs with a single linear budget constraint.

Step 2: Turn the target into a \(Q\)-budget constraint

Let

$A = \{\omega : X(\omega) \ge T\}$

be the success event. On that event we have \(X(\omega) \ge T\), so

$1 \ge E_Q[X] \ge E_Q[T \cdot 1_A] = T \, Q(A).$

Hence every feasible strategy obeys

$Q(A) \le \frac{1}{T}.$

Conversely, if an event \(A\) satisfies \(Q(A) \le 1/T\), then the digital payoff

$X(\omega) = T \cdot 1_A(\omega)$

has cost \(TQ(A) \le 1\), so it is feasible and succeeds exactly on \(A\). Therefore the original problem is exactly equivalent to

$\max_A P(A) \quad \text{subject to} \quad Q(A) \le \frac{1}{T}.$

This is a Neyman-Pearson type optimization problem.

Step 3: Collapse the state space by the number of wins

Let \(W\) be the number of wins along the path. Under the fair measure \(Q\),

$q_w = Q(W=w) = \binom{N}{w} 2^{-N}.$

Under the true measure \(P\),

$p_w = P(W=w) = \binom{N}{w} p^w (1-p)^{N-w}.$

All paths with the same \(w\) have the same price under \(Q\) and the same probability under \(P\). So instead of choosing individual paths, we only need to choose how much of each win-count layer \(w\) to include.

Step 4: Order the layers by likelihood ratio

The relevant ranking statistic is the likelihood ratio

$\frac{p_w}{q_w} = (2p)^w \bigl(2(1-p)\bigr)^{N-w}.$

For this problem \(p=0.6\), so \(p/(1-p)=1.5>1\). As \(w\) increases by \(1\), the ratio is multiplied by

$\frac{p}{1-p} > 1.$

Therefore \(\frac{p_w}{q_w}\) is strictly increasing in \(w\). The optimal success set must thus take the largest \(w\)-layers first: all states with \(W=N\), then \(W=N-1\), and so on, because those layers give the most true probability per unit of fair-cost budget.

Step 5: Use a boundary fraction to fill the budget exactly

Let

$B = \frac{1}{T}.$

We accumulate \(Q\)-mass from \(w=N\) downward until the next full layer would exceed \(B\). Suppose \(w_*\) is the boundary layer. Then every layer with \(w > w_*\) is taken completely, and only a fraction

$\eta = \frac{B - \sum_{w=w_*+1}^{N} q_w}{q_{w_*}}$

of layer \(w_*\) is needed, with \(0 \le \eta \le 1\). The optimal success probability is therefore

$\sum_{w=w_*+1}^{N} p_w + \eta p_{w_*}.$

This is exactly the form implemented by the program.

Worked Example: \(N=2\), \(p=0.6\), \(T=2\)

Here the budget is \(B=1/2\). Under the fair measure \(Q\),

$q_2 = \frac{1}{4}, \qquad q_1 = \frac{1}{2}, \qquad q_0 = \frac{1}{4}.$

Under the true measure \(P\),

$p_2 = 0.6^2 = 0.36, \qquad p_1 = 2(0.6)(0.4) = 0.48, \qquad p_0 = 0.4^2 = 0.16.$

We take the \(w=2\) layer completely, using \(Q\)-mass \(1/4\). The remaining budget is \(1/4\), so we take

$\eta = \frac{1/2 - 1/4}{1/2} = \frac{1}{2}$

of the \(w=1\) layer. Hence the optimal success probability is

$0.36 + \frac{1}{2}\cdot 0.48 = 0.60.$

This matches the small validation case embedded in the implementations.

How the Code Works

The implementations first handle the trivial case \(T \le 1\), where success is guaranteed. Otherwise they set the fair-cost budget to \(1/T\) and build the entire fair layer distribution \((q_0,\dots,q_N)\) using the stable binomial recurrence

$q_0 = 2^{-N}, \qquad q_{w+1} = q_w \frac{N-w}{w+1}.$

Next they recover the true distribution \((p_0,\dots,p_N)\) from the same layers via

$p_w = q_w \bigl(2(1-p)\bigr)^N \left(\frac{p}{1-p}\right)^w,$

which avoids direct factorials and keeps the arithmetic numerically stable. Finally they scan from \(w=N\) down to \(0\), add whole layers while the \(Q\)-budget allows it, identify the first layer that would overflow the budget, and then add the needed boundary fraction from that layer. The C++, Python, and Java implementations all follow this same logic, differing only in their numeric types.

Complexity Analysis

Building the two arrays of layer masses takes \(O(N)\) time, and the final downward scan also takes \(O(N)\) time. Because the implementations store the \(Q\)-distribution and the \(P\)-distribution explicitly for all \(N+1\) win counts, the memory usage is \(O(N)\). For the actual instance \(N=1000\), this is easily manageable.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=765
2. Neyman-Pearson lemma: Wikipedia — Neyman-Pearson lemma
3. Binomial distribution: Wikipedia — Binomial distribution
4. Likelihood-ratio test: Wikipedia — Likelihood-ratio test
5. Risk-neutral measure: Wikipedia — Risk-neutral measure