Detailed mathematical approach

Problem Summary

There are \(N=50\) shots. On shot \(x\), the hit probability depends on an unknown parameter \(q\):

$p_x(q)=1-\frac{x}{q},\qquad x=1,2,\dots,50.$

We must find the value of \(q\) for which the probability of getting exactly \(20\) hits is

$0.02.$

The final numeric Project Euler answer is intentionally omitted here.

Mathematical Approach

1) Basic constraints on \(q\). To keep every hit probability between \(0\) and \(1\), we need

$q>50.$

The expected number of hits is

$\mu(q)=\sum_{x=1}^{50}\left(1-\frac{x}{q}\right)=50-\frac{1275}{q}.$

So even when \(q\downarrow 50\), the mean is already above \(24.5\). Since the target score is only \(20\), we are searching for a left-tail probability.

2) This is a Poisson-binomial distribution. The 50 shots are independent, but the success probabilities are different. Therefore the total number of hits is not binomial; it is a Poisson-binomial random variable.

A useful generating-function view is

$G(z)=\prod_{x=1}^{50}\bigl((1-p_x)+p_x z\bigr).$

The coefficient of \(z^s\) in \(G(z)\) is exactly the probability of finishing with \(s\) hits.

3) Exact DP recurrence. Let \(P_x(s)\) be the probability of having exactly \(s\) hits after the first \(x\) shots. For shot \(x\), either we miss and stay at \(s\), or we hit and come from \(s-1\). Hence

$P_x(s)=P_{x-1}(s)(1-p_x)+P_{x-1}(s-1)p_x.$

The base conditions are

$P_0(0)=1,\qquad P_0(s>0)=0.$

The target function is therefore

$F(q)=P_{50}(20).$

This is what exact_score_probability computes.

4) Why a 1D array is enough. At step \(x\), the new value of \(P_x(s)\) depends only on the previous-layer values \(P_{x-1}(s)\) and \(P_{x-1}(s-1)\). So we can update a single array in place by running \(s\) downward:

$s=x,x-1,\dots,1.$

That preserves the old layer until it has been used.

5) Tiny worked example. After two shots, the probability of exactly one hit is

$P_2(1)=p_1(1-p_2)+(1-p_1)p_2.$

This is the same recurrence in miniature: either the first shot hits and the second misses, or the first misses and the second hits.

6) Root search. We need to solve

$F(q)=0.02.$

The code first brackets the solution. Its checkpoint verifies that

$F(52)\approx 0.0240157724>0.02,\qquad F(53)\approx 0.0180966946<0.02.$

So the desired \(q\) lies strictly between \(52\) and \(53\).

As \(q\) increases, every individual hit probability \(p_x(q)\) increases, so the whole score distribution shifts toward larger totals. Since \(20\) is already well below the mean throughout the relevant range, the exact-\(20\) probability decreases across the bracket. That makes bisection the natural method.

7) Why bisection is reliable here. Once we have an interval \([L,H]\) with

$F(L)>0.02>F(H),$

we repeatedly test the midpoint \(M=(L+H)/2\). If \(F(M)\) is still above the target, the root is to the right; otherwise it is to the left. Repeating this around 220 times drives the interval width far below the requested decimal precision.

Complexity Analysis

One evaluation of \(F(q)\) uses the DP over \(50\) shots and score states \(0,\dots,20\), so the cost is

$O(NS),\qquad N=50,\ S=20,$

which is tiny. With \(I\) bisection iterations, total time is

$O(INS),$

and memory usage is

$O(S).$

Numerically, the update is stable because every new value is a convex combination of probabilities in \([0,1]\).

Further Reading

1. Problem page: https://projecteuler.net/problem=286
2. Poisson-binomial distribution: https://en.wikipedia.org/wiki/Poisson_binomial_distribution
3. Bisection method: https://en.wikipedia.org/wiki/Bisection_method