Solution

Answer: 40.66368097

Let the three-digit part of a licence plate be the random variable $X\in{000,\dots,999}$.

Seth wins as soon as he has seen two plates whose numbers sum to $1000$.

The key subtlety is:

$000$ can never participate in a win (it would need $1000$, which is impossible).
$500$ is special: it pairs with itself, so Seth needs to see two occurrences of $500$.

So this is not the standard coupon collector problem.

Mathematical analysis

There are:

$499$ complementary pairs

$$(1,999),(2,998),\dots,(499,501)$$

one self-pair:

$$(500,500)$$

We track the process using states.

State description

Let

$k$ = number of complementary pairs for which Seth has seen exactly one member.
$h\in{0,1}$:
$h=0$: Seth has not yet seen a $500$,
$h=1$: Seth has seen exactly one $500$.

Define

$$E(k,h)$$

as the expected additional number of plates needed to win from this state.

Initially:

$$E(0,0)$$

is the quantity we want.

Transition probabilities

From state $(k,h)$:

1. Immediate win

A win occurs if:

Seth sees the complement of one of the $k$ active pairs,
or (if $h=1$) he sees another $500$.

Thus

$$p_{\text{win}}=\frac{k+h}{1000}.$$

2. Create a new active pair

There are $499-k$ untouched complementary pairs, each contributing two unseen numbers.

Hence:

$$p_{\text{new}}=\frac{2(499-k)}{1000}.$$

This moves to:

$$(k+1,h).$$

3. First appearance of $500$

If $h=0$, seeing $500$ changes state to $(k,1)$:

$$p_{500}=\frac{1}{1000}.$$

If $h=1$, another $500$ would already be counted as a win.

4. Everything else

All remaining outcomes leave the state unchanged.

Expected value equation

Condition on the next plate:

$$E(k,h) = 1 + p_{\text{stay}}E(k,h) + p_{\text{new}}E(k+1,h) + p_{500}E(k,1).$$

Rearrange:

$$E(k,h) = \frac{ 1 + p_{\text{new}}E(k+1,h) + p_{500}E(k,1) }{ 1-p_{\text{stay}} }.$$

But

$$1-p_{\text{stay}} = p_{\text{win}}+p_{\text{new}}+p_{500}.$$

This gives a simple backward recursion.

Python implementation

from functools import cache

@cache
def E(k, h):
    """
    Expected remaining plates needed to win.

    k = number of complementary pairs where exactly one member
        has been seen.
    h = 0 or 1 depending on whether one '500' has been seen.
    """

    # Probability of immediate win
    p_win = (k + h) / 1000.0

    # Probability of creating a new active pair
    p_new = 2 * (499 - k) / 1000.0

    # Probability of seeing the first 500
    p_500 = 0.0 if h else 1 / 1000.0

    # Probability of staying in same state
    p_stay = 1.0 - p_win - p_new - p_500

    # Recursive expectation equation
    value = 1.0

    if k < 499:
        value += p_new * E(k + 1, h)

    if h == 0:
        value += p_500 * E(k, 1)

    return value / (1.0 - p_stay)

answer = E(0, 0)

print("{:.8f}".format(answer))

Code walkthrough

Memoization

@cache

stores previously computed states so each state is solved once.

Probabilities

p_win = (k + h) / 1000.0

$k$ winning complements,
plus one extra winning possibility if we've already seen a $500$.

p_new = 2 * (499 - k) / 1000.0

Each untouched pair contributes two unused numbers.

p_500 = 0.0 if h else 1 / 1000.0

The first $500$ changes state; the second wins immediately.

Expectation equation

return value / (1.0 - p_stay)

comes from solving:

$$E = 1 + p_{\text{stay}}E + \cdots$$

for $E$.

Numerical result

Running the program gives:

$$40.6636809666\ldots$$

Rounded to 8 decimal places:

$$40.66368097$$

This magnitude makes sense:

a random matching event among 1000 possibilities should occur after roughly $O(\sqrt{1000})$ samples (birthday-paradox behavior),
and $40.66$ is indeed close to $\sqrt{\pi\cdot1000/2}\approx39.6$.

Answer: 40.66368097

Project Euler Problem 371