Detailed mathematical approach

Problem Summary

A gambler starts with capital \(1\). In each of \(n\) fair tosses, the gambler bets the same fixed fraction \(f\) of the current capital. A win triples the stake portion, so total capital is multiplied by \((1+2f)\); a loss destroys the stake portion, so total capital is multiplied by \((1-f)\).

For the original Project Euler problem, \(n=1000\) and the target is \(T=10^9\). The C++ solution keeps both quantities as parameters, so the same derivation works for any \(n\ge 1\) and \(T>1\).

Mathematical Approach

1. Wealth After Exactly \(k\) Wins

If exactly \(k\) of the \(n\) tosses are wins, then the order of wins and losses does not matter, because multiplication is commutative. The final wealth is therefore

$W_k(f)=(1+2f)^k(1-f)^{n-k}.$

So for each possible win count \(k\), the problem is a one-variable optimization over the admissible range \(0\le f<1\).

2. Why the Code Optimizes the Logarithm

Directly maximizing \(W_k(f)\) is equivalent to maximizing its logarithm, because \(\ln(x)\) is strictly increasing on \(x>0\). The code therefore works with

$g_k(f)=\ln W_k(f)=k\ln(1+2f)+(n-k)\ln(1-f).$

This removes huge intermediate numbers and turns the product into a sum. It also makes the derivative easy to analyze.

3. Best Fixed Fraction for a Given \(k\)

Differentiating gives

$g_k'(f)=\frac{2k}{1+2f}-\frac{n-k}{1-f}.$

Setting the derivative to zero yields the critical point

$f_*=\frac{3k-n}{2n}.$

The second derivative is

$g_k''(f)=-\frac{4k}{(1+2f)^2}-\frac{n-k}{(1-f)^2}<0,$

so \(g_k\) is concave and any interior critical point is automatically the global maximum.

This gives exactly the three branches used in minimum_wins_needed:

1. If \(k=n\), then every toss is a win, so \(W_n(f)=(1+2f)^n\) is increasing and the optimum is the boundary limit \(f\to1^{-}\), giving \(\max g_n = n\ln 3\).

2. If \(f_*\le 0\), then the concave maximum lies to the left of the admissible interval, so the best admissible point is \(f=0\), with \(W_k(0)=1\) and therefore \(g_k(0)=0\).

3. If \(0<f_*<1\), then the optimum is achieved at that interior point and the code evaluates \(g_k(f_*)\) directly.

4. Turning Optimization into a Threshold in \(k\)

For a fixed admissible \(f\), replacing one loss by one win multiplies wealth by

$\frac{1+2f}{1-f}>1 \qquad (0<f<1).$

So for every fixed \(f\), the quantity \(W_k(f)\) is nondecreasing in \(k\), and strictly increasing when \(f>0\). Taking the maximum over all admissible \(f\) preserves this monotonicity, so \(\max_f g_k(f)\) also increases with \(k\).

That means there is a clean threshold \(k_{\min}\): the smallest number of wins for which the target becomes reachable, namely

$k_{\min}=\min\{k:\max_f g_k(f)\ge \ln T\}.$

Once this threshold is found, every outcome with at least \(k_{\min}\) wins is successful, and every outcome below it is impossible to rescue with any fixed fraction.

5. The Probability Is a Binomial Tail

Because the tosses are fair, the number of wins \(K\) follows

$K\sim\mathrm{Binomial}(n,1/2).$

Therefore the answer is

$P_{\mathrm{succ}}=\Pr[K\ge k_{\min}]=\sum_{k=k_{\min}}^{n}\binom{n}{k}2^{-n}.$

The program does not compute factorials. Instead it starts with

$P_0=2^{-n}$

and uses the recurrence

$P_{k+1}=P_k\frac{n-k}{k+1}.$

This is the standard ratio between consecutive binomial masses and is much more stable numerically.

6. Worked Checkpoint: \(n=2,\;T=2\)

The code contains this test and expects the answer \(1/4\). Let us derive it exactly.

If \(k=1\), then

$f_*=\frac{3\cdot1-2}{2\cdot2}=\frac14.$

At this optimum,

$W_1\!\left(\frac14\right)=\left(1+\frac12\right)\left(1-\frac14\right)=\frac32\cdot\frac34=\frac98<2.$

So one win is not enough.

If \(k=2\), then every toss is a win and the optimum is the boundary \(f\to1^{-}\), where

$W_2(f)\to 3^2=9>2.$

Hence \(k_{\min}=2\). The success probability is just the probability of two wins in two fair tosses:

$P_{\mathrm{succ}}=\binom22 2^{-2}=\frac14.$

7. Worked Checkpoint: \(n=4,\;T=4\)

The second internal test expects \(5/16\). Again we can derive it by hand.

If \(k=2\), then

$f_*=\frac{3\cdot2-4}{2\cdot4}=\frac14,$

so

$W_2\!\left(\frac14\right)=\left(\frac32\right)^2\left(\frac34\right)^2=\frac{81}{64}<4.$

Thus two wins are still insufficient.

If \(k=3\), then

$f_*=\frac{3\cdot3-4}{2\cdot4}=\frac58,$

and

$W_3\!\left(\frac58\right)=\left(1+\frac{10}{8}\right)^3\left(1-\frac58\right)=\left(\frac94\right)^3\frac38=\frac{2187}{512}>4.$

Therefore \(k_{\min}=3\). The success probability is the binomial tail

$\Pr[K\ge3]=\binom43 2^{-4}+\binom44 2^{-4}=\frac{4+1}{16}=\frac{5}{16}.$

How the Code Works

parse_arguments reads three command-line controls: --tosses=<n>, --target=<T>, and --skip-checkpoints.

minimum_wins_needed scans \(k=0,1,\dots,n\). For each \(k\), it computes the best possible log-wealth according to the three-case rule above. The first \(k\) whose best log-wealth reaches \(\ln T\) is returned.

binomial_tail_probability builds the probabilities \(P_k=\Pr[K=k]\) from \(P_0=2^{-n}\) using the binomial ratio recurrence, then sums from \(k_{\min}\) to \(n\).

solve_probability is just the composition of those two steps. The two checkpoints in run_checkpoints verify that both the threshold search and the tail summation are working correctly before the main Euler instance is evaluated.

Complexity Analysis

The threshold search over \(k\) is \(O(n)\). Building and summing the binomial probabilities is also \(O(n)\). The implementation stores a probability vector of length \(n+1\), so the memory usage is \(O(n)\).

A streaming implementation could reduce the memory to \(O(1)\), because only the current probability is needed, but the vector version is simpler to read and perfectly adequate for \(n=1000\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=267
2. Kelly criterion intuition: Wikipedia - Kelly criterion
3. Binomial distribution: Wikipedia - Binomial distribution