Project Euler Problem 371

Question

Project Euler Problem 371 states

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: You may assume each licence plate seen is equally likely to have any three digit number on it.

I thought this would be quite simple but I can't seem to get it right. The way I've approached it is as follows:

• If we imagine that we are sampling from a bag of balls without replacement, we need to know given all of the previous balls sampled, what the probability of a win is.

• The total number of unique plates is $T = 26^3 \times 10^3 = 17,576,000$ under the assumption that plates such as ABC-000 are allowed (the question doesn't say they aren't).

• For any given letter combination, there are $499$ possible wins (such as {ABC-003,ABC-997}) $(001+999),(002+998),...,(499+501)$ as duplicates aren't allowed (i.e. {ABC-500,ABC-500}), and between any two letter combinations there are $500$ possible wins as {ABC-500,DEF-500} is allowed.

• Given we have drawn a plate, the probability that the next plate (now we have seen two, $n=2$) is a win is:

$$Pr(win | n=2) = \frac{((26^3-1) \times \frac{500}{10000}) + (1 \times \frac{499}{999})}{26^3} \approx 0.0500$$

and then assuming that we didn't win, the probability when we see the next plate, assuming that the two letter combinations $c_1$ and $c_2$ were different is:

$$Pr(win | n=3, c_1 \neq c_2) = 2 \times \frac{((26^3-1) \times \frac{500}{10000}) + (1 \times \frac{499}{999})}{26^3 - 1}$$

and if they were the same:

$$Pr(win | n=3, c_1 = c_2) = 2 \times \frac{((26^3-1) \times \frac{500}{10000}) + (1 \times \frac{499}{998})}{26^3 - 1}$$

And then for the next one, we have to work out the probability that plate has the same letter combination as one (or more) of the previous ones and it starts to get really horrible!

Even then we're not done, as we have to then work out how many draws we'd expect to do before we win.

So where am I going wrong?

As an aside, I've written some python code to do monte-carlo draws, and it comes out to around 40.66...

Answer 1

You misunderstood the problem.

Just assume encountering any three-digit number is equally likely regardless of history. You can completely ignore the letters.

(I believe I'm not doing any wrong by saying this here.)

Answer 2

All numbers from 0 to 999 are equally likely.

Assume you have seen k different non-zero numbers so far. (Non-zero because a zero license plate won't help you winning). When you see the next license plate you either win, or you see a number that you haven't seen before, or you see a number that is either zero or that you have already seen.

Write a program that tells you all the probabilities after seeing 1, 2, 3, 4, 5 ... cars, detects the probability of winning in round x, and adds things to get an expected value for the number of rounds until winning. It is typical for Euler problems that you need a computer that runs for a considerable time to get the solution.

And then ... you throw the result away and think very hard about the number 500 and how it affects the result just a little bit, but enough to make your first answer unacceptable.