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...

  • 3
    $\begingroup$ You are to be commended for doing so much work, for presenting it as part of your question, and for sourcing the question to Project Euler. However, the Project Euler people have made it clear that they don't want websites like this one to give help on their problems. $\endgroup$ – Gerry Myerson Feb 17 '12 at 3:58
  • $\begingroup$ Ok sorry, but I had seen similar questions on 7 or so other PE Problems. It was more for my understanding - my Monte Carlo estimate is still churning away (I have 4 d.p. now, need to get 8), so I will get an answer! Also note that if you want to cheat, many of the answers can be found by plugging them directly into Wolfram Alpha (Problem 3) $\endgroup$ – tdc Feb 17 '12 at 11:24
  • 1
    $\begingroup$ Just wanted to reinforce what Gerry said, this is a great model for how a question from another source should be asked here. I don't think this question and ngn's answer are against the spirit of PE. In the future though, it'd probably be better to ask a question like this (where you have good evidence that you misunderstood the question somehow) at PE's question board. $\endgroup$ – Noah Snyder Oct 16 '12 at 15:02

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.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.