Detailed mathematical approach

Problem Summary

In the original problem we observe random three-digit licence plates from 000 to 999. We stop as soon as two observed plates sum to \(1000\). The local solvers generalize the setting to any odd maximum \(M\), so the available values are \(\{0,1,\dots,M\}\) and the target sum is \(M+1\). For the Project Euler input \(M=999\), the program computes the expected stopping time and prints it to eight decimal places.

Mathematical Approach

Step 1: Partition the Numbers

Let

$N=M+1,\qquad m=\frac{M-1}{2},\qquad s=\frac{M+1}{2}.$

Then the numbers split into three types. For each \(1\le i\le m\) we have one complementary pair

$P_i=\{i,N-i\}.$

There are \(m\) such pairs, one self-complementary value \(s\) because \(s+s=N\), and the singleton \(0\), whose complement \(N\) lies outside the range. When \(M=999\), this means \(499\) ordinary pairs, the special value \(500\), and the harmless value \(000\).

Step 2: Compress the State Space

Before the game ends, an ordinary pair can only be in two relevant conditions: unopened, meaning neither side has appeared yet, or half-open, meaning exactly one side has appeared. A fully completed pair would already end the process, so it never appears inside the recurrence.

Therefore the detailed identity of the opened pairs does not matter. We only need:

\(k\): the number of half-open pairs, and a binary flag telling us whether \(s\) has already appeared once.

Define \(E_0[k]\) as the expected remaining number of draws when \(k\) ordinary pairs are half-open and \(s\) has not been seen. Define \(E_1[k]\) as the same expectation when \(s\) has been seen exactly once. This is the exact meaning of the arrays e0 and e1 in the C++, Python, and Java solutions.

Step 3: First-Step Equation for \(E_1[k]\)

Assume we are in state \(E_1[k]\). Then:

The draw \(0\) keeps the state unchanged. For each of the \(k\) half-open pairs, drawing the already seen side also keeps the state unchanged. So there are \(k+1\) same-state outcomes.

Drawing \(s\) again wins immediately. For each of the \(k\) half-open pairs, drawing the missing complement also wins immediately. So there are \(k+1\) winning outcomes.

The remaining \(m-k\) pairs are unopened. Any one of their \(2(m-k)\) numbers opens a new pair, so the process moves to \(E_1[k+1]\).

First-step analysis therefore gives

$E_1[k]=1+\frac{k+1}{N}E_1[k]+\frac{2(m-k)}{N}E_1[k+1].$

Moving the same-state term to the left yields the recurrence implemented in the code:

$\boxed{E_1[k]=\frac{N+2(m-k)E_1[k+1]}{N-(k+1)}}.$

The denominator \(N-(k+1)\) is exactly the variable den in the source files. It appears because we subtract the probability of staying in the same state from the left-hand side.

Step 4: First-Step Equation for \(E_0[k]\)

Now assume \(s\) has not appeared yet. The same-state outcomes are still \(0\) plus the already seen sides of the \(k\) half-open pairs, so again there are \(k+1\) of them.

Drawing the missing complement of one of the \(k\) half-open pairs wins immediately. Drawing \(s\) does not win yet; it changes the state from \(E_0[k]\) to \(E_1[k]\). Finally, any number from one of the \(m-k\) unopened pairs moves the process to \(E_0[k+1]\).

Hence

$E_0[k]=1+\frac{k+1}{N}E_0[k]+\frac{1}{N}E_1[k]+\frac{2(m-k)}{N}E_0[k+1],$

so

$\boxed{E_0[k]=\frac{N+2(m-k)E_0[k+1]+E_1[k]}{N-(k+1)}}.$

Step 5: Boundary Condition and Final Answer

When \(k=m\), every ordinary pair is already half-open, so there is no transition to \(k+1\). The recurrence becomes

$E_1[m]=\frac{N}{N-(m+1)}=\frac{2m+2}{m+1}=2,$

$E_0[m]=\frac{N+E_1[m]}{N-(m+1)}=\frac{2m+4}{m+1}.$

From there we sweep backward for \(k=m-1,m-2,\dots,0\). The required expectation is

$\boxed{E_0[0]}. $

Checkpoint Example: \(M=3\)

This is the exact case hard-coded in the C++ verification. Here \(N=4\), there is one ordinary pair \(\{1,3\}\), the special value \(2\), and the inert value \(0\). The backward recurrence gives

$E_1[1]=2,\qquad E_0[1]=3,$

$E_1[0]=\frac{4+2E_1[1]}{3}=\frac{8}{3},$

$E_0[0]=\frac{4+2E_0[1]+E_1[0]}{3}=\frac{38}{9}.$

This matches the checkpoint in Euler371.cpp. For the real input \(M=999\), the same recurrence with \(m=499\) gives

$E_0[0]\approx 40.66368097.$

How the Code Works

All three solution files implement the same compressed dynamic program. They compute pairCount = (maxNumber - 1) / 2, set totalNumbers = 2 * pairCount + 2, allocate arrays e0 and e1, and iterate \(k\) downward from pairCount to \(0\).

The helper quantities are

$\texttt{grow}=2(\texttt{pairCount}-k),\qquad \texttt{den}=\texttt{totalNumbers}-(k+1).$

Here grow counts the numbers that belong to still unopened pairs and therefore increase \(k\) by one. Then the code applies the two boxed recurrences above. The final formatted result is e0[0].

The C++ file also contains an explicit-state verifier for tiny instances. In that checker, every pair has three microstates: unseen, left side seen, or right side seen. Together with the flag for whether \(s\) has been seen, this creates \(2\cdot 3^m\) states. The program builds the linear system for those exact Markov expectations, solves it by Gaussian elimination, and confirms that the compressed recurrence agrees for \(m=2\) and \(m=3\).

Complexity Analysis

Let \(m=(M-1)/2\). The implemented recurrence evaluates each \(k\) once, so the running time is \(O(m)\). The current implementations store two arrays of length \(m+1\), hence \(O(m)\) memory. The explicit-state verifier is exponential in \(m\) and is only used for very small checkpoint cases.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=371
2. First-step analysis: Wikipedia — First-step analysis
3. Markov chains and expected hitting times: Wikipedia — Markov chain
4. Dynamic programming overview: Wikipedia — Dynamic programming