Solution

Answer: 52.6494571953

Let

$$p_x = 1 - \frac{x}{q}$$

be the probability that Barbara scores from distance $x$, where $x=1,2,\dots,50$.

We are told that the probability of scoring exactly 20 points in the 50 shots is exactly $2%$:

$$\Pr(\text{exactly 20 successes}) = 0.02.$$

We must determine $q>50$.

Mathematical analysis

For each shot $x$:

success probability:

$$p_x = 1-\frac{x}{q}$$

miss probability:

$$1-p_x = \frac{x}{q}.$$

The shots are independent, but the probabilities are different for each shot, so this is not a standard binomial distribution.

We therefore use dynamic programming.

DP formulation

Define

$$dp[k][s]$$

as the probability that after considering the first $k$ shots, Barbara has scored exactly $s$ points.

Initial condition:

$$dp[0][0]=1$$

since before any shots, the probability of 0 successes is 1.

For shot $k$:

with probability $p_k$, the score increases by 1,
with probability $1-p_k$, it stays the same.

Therefore,

$$dp[k][s] = dp[k-1][s-1]\cdot p_k + dp[k-1][s]\cdot (1-p_k).$$

After processing all 50 shots:

$$P(q)=dp[50][20].$$

We must solve

$$P(q)=0.02.$$

Monotonicity

As $q$ increases:

$$p_x = 1-\frac{x}{q}$$

increases for every shot.

So the expected number of successes rises, meaning the probability of getting exactly 20 successes eventually decreases (because the mean moves above 20).

Numerically:

$P(52)\approx 0.0240$
$P(55)\approx 0.0101$

Hence the solution lies between 52 and 55.

We can therefore use binary search.

Python implementation

from math import *

def probability(q):
    # dp[s] = probability of exactly s successes so far
    dp = [0.0] * 21
    dp[0] = 1.0

    # shots from x = 1..50
    for x in range(1, 51):
        p = 1.0 - x / q

        new_dp = [0.0] * 21

        # zero successes case
        new_dp[0] = dp[0] * (1 - p)

        for s in range(1, 21):
            # make shot x
            make = dp[s - 1] * p

            # miss shot x
            miss = dp[s] * (1 - p)

            new_dp[s] = make + miss

        dp = new_dp

    return dp[20]

# Binary search for q
lo = 50.0
hi = 60.0

for _ in range(100):
    mid = (lo + hi) / 2

    if probability(mid) > 0.02:
        lo = mid
    else:
        hi = mid

q = (lo + hi) / 2

print("{:.10f}".format(q))

Code walkthrough

`probability(q)`

Computes the probability of exactly 20 successes.

We store only one DP row at a time:

dp[s]

represents the probability of exactly s successes after processing some shots.

Transition

For each shot:

make = dp[s - 1] * p
miss = dp[s] * (1 - p)

These correspond to:

reaching s by making the current shot,
reaching s by missing the current shot.

Binary search

We search for the unique $q$ satisfying

$$P(q)=0.02.$$

If:

probability(mid) > 0.02

then $q$ is too small, so we move the lower bound upward.

After 100 iterations, the value is accurate far beyond $10^{-10}$.

Final verification

The computed value is:

$$q \approx 52.6494571953$$

Check:

$q>50$ ✔
$P(q)\approx 0.02$ ✔
Nearby values:
$q=52\Rightarrow P>0.02$
$q=55\Rightarrow P<0.02$

So the solution is consistent.

Answer: 52.6494571953

Project Euler Problem 286