Project Euler Problem 371 Solution

Project Euler Problem 371 Statement

Oregon licence plates consist of three letters followed by a three digit number (each digit can be from [0..9]).
While driving to work Seth plays the following game:
Whenever the numbers of two licence plates seen on his trip add to 1000 that's a win.

E.g. MIC-012 and HAN-988 is a win and RYU-500 and SET-500 too (as long as he sees them in the same trip).

Find the expected number of plates he needs to see for a win.
Give your answer rounded to 8 decimal places behind the decimal point.

Note: We assume that each licence plate seen is equally likely to have any three digit number on it.

Solution

Project Euler Problem 371 overview:

Seth plays a game where he wins if the three-digit numbers on any two Oregon license plates he sees on a trip add to 1000, and you must find the expected number of plates he needs to see for this to happen, assuming all three-digit combinations are equally likely.

Solution Summary

This computes the expected number of random license plates needed until two seen plates sum to 1000. It models the process with dynamic programming over C, the count of “open” complementary pairs among the 499 pairs (x, 1000−x). Because 500 pairs with itself, it keeps two expectations: P1 when 500 hasn’t appeared and P2 when it has. Iterating C backward, the recurrences average over 1000 equally likely next plates, updating P2 first then P1. The final P1 at C=0 is the answer.

The Dynamic Programming Approach

The solution uses backward induction to compute expected values. The variables P1 and P2 represent expected values that are iteratively updated, where P1 ultimately gives us the expected number of plates to be created. The variable C represents the number of plates already created, starting from 1 and going up to 499 as the loop counter k decreases from 498 to 0.

We can work backwards from states where many plates already exist to the initial state where no plates exist. This is more efficient than trying to simulate the process forward, as the expected values at each state depend on the expected values of future states.

The Recurrence Relations

The two update formulas are derived from the probabilistic transitions in the plate creation process:

P2 = (2*C*P2 + 1000) / (C + 500)
P1 = (2*C*P1 + P2 + 1000) / (C + 500)

These equations encode the probability of getting duplicate combinations versus new ones. The constant 1000 represents the total number of possible 3-digit numbers, while the terms involving C capture how the probability of duplicates increases as more plates are created. The factor of 500 in the denominator comes from the specific probability calculations for this problem's constraints.

The mathematical foundation here is Markov chain analysis, where each state (number of plates created) has specific transition probabilities to other states. By solving the system of expected value equations backwards and starting with boundary conditions of P1=0 and P2=0, the algorithm efficiently computes the answer.

After all iterations complete, P1 contains the expected number of license plates that will be created.

P1,P2 = 0,0

for k in range(498, -1, -1):
    C = 499 - k
    P2 = (2*C*P2 + 1000) / (C + 500)
    P1 = (2*C*P1 + P2 + 1000) / (C + 500)
    
print(f"{P1:.8f}")