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-000are 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…
Best Answer
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.)