Problem 371

[thundre]

That makes sense. What level of Math do you think the "average" person would need to complete a problem like 371? Is it even remotely possible for someone with just Calculus II knowledge and a bit of Linear Algebra to solve a problem like this? (I'm a college freshmen, but these problems intrigue me so much!!)

This problem can be solved using basic probability, if you have the right insight.

[viv_ban]

I am having issues with precision. Can somebody suggest me how to get over the problem of precision. I have tried logarithm-antilogarithm to approximate but it does not give correct answer.

[thundre]

I am having issues with precision. Can somebody suggest me how to get over the problem of precision. I have tried logarithm-antilogarithm to approximate but it does not give correct answer.

Lately I've been using the BigFraction class from the Apache Commons Math library. Although for this problem the doubleValue() method failed me; I had to find another way to get the required decimal answer. (I submitted a bug-fix which should be in release 3.0.)

[sivakd]

There are solutions in C++ using just double. So, you don't need anything more than that.

I am having issues with precision. Can somebody suggest me how to get over the problem of precision. I have tried logarithm-antilogarithm to approximate but it does not give correct answer.

[PurpleBlu3s]

I have only been able to get a formula that works with integers - and it doesn't extend to reals. Is it possible to come up with a formula to work with reals or does one need to find the two integers the answer lies between and do something else from there?

[PurpleBlu3s]

Can anyone confirm the probability of not having a win after seeing 10 plates is 0.95586930 (8 s.f.)?

[thundre]

I have only been able to get a formula that works with integers - and it doesn't extend to reals. Is it possible to come up with a formula to work with reals or does one need to find the two integers the answer lies between and do something else from there?

Being able to calculate the probability of a win at each step is an OK start. But there is a certain concept you need to apply to finish this problem. Saying what it is would be a spoiler, so I'll just say I used the same concept in problems 280, 316, 339, and 367.

[gnome]

I finally solved this and hopefully no one would object if I write the statement "ignore that the license plates have letters completely, just assume there are 3 digit license plates and many cars can have the same 3 digits such that the probability of seeing any number is the same for any i^th car seen". It may be same as the Note: provided in the problem, but for people who have difficulty understanding the note ...

Thanks for that comment! I solved the harder problem first, thinking that Seth keeps a notebook where he writes down any license plate he sees, and does not count plates he has seen before. (Safety notice: do not take notes while driving. I cannot be held liable for any property damage or physical injury.)

So this would have been the right interpretation:

Whenever the numbers of two (not necessarily different) licence plates seen on his trip add to 1000 that's a win.

[thkang]

500 is a curious number..

[jake223]

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

There shouldn't be a period between "SET-500 too" and "(as long" (I think).

[oleglyamin]

I'm confused by seemingly contradicting statements in this thread.

On one hand

So why isn't this just a Bernoulli random variable with p = 999 / 1000000?

It's not a Bernoulli random variable because p depends on what happened in the previous trials.

On the other

If so, for example, SET-500 and SET-500 will be a win. Right?

Right. Even if it's XYZ-500 and ABC-500, or any other letter combinations.

The last quote implies that the same license plate can be "re-drawn" many times. Doesn't it contradict the first quote, which says that the probability of seeing certain number on a license plate depends on what happened in the previous trials? Which is it? I'm not asking for any clues, I'm just trying to make sense of the problem.

[thundre]

The inputs are independent. The probability of seeing a given number at a given time is 1/1000.

What I was saying was that the probability of a win at (for example) the 6th license plate depends on the values of the first 5 plates -- in particular, whether any were duplicated.

[demongolem]

Ah good, so you can see the same license plate twice, which I am curious as to why the original problem does not state one way or the other in some form.

But just one more question while I am it. So, the license plate of Seth is irrelevant? For all we know, he could be driving a car with Washington plates?

[oleglyamin]

Could someone go to this problem's closed forum and answer the question in my last post? Thanks.

[RishadanPort]

This probably has already been explained in this thread, -- but I want clarity...

Is it possible for him to see the license plate SET-500, and SET-500 (resulting in a win) on the same trip or not?


in my algorithm, I treat that as allowed, and I'm fairly certain it is done correctly-- however the projecteuler does not accept my answer.

[RishadanPort]

I'm not sure if this is the right place to ask this...

But lets suppose we see the numbers 1-500 already.
Would the expected number of plates to see for a win be 2, or am I missing something.

[RishadanPort]

Nevermind I figured out why...

Indeed 500 is a magic number.

[hamsterofdeath]

how is "expected to win" defined exactly? the chance of seeing a pair must be >50%?

[Animus]

how is "expected to win" defined exactly? the chance of seeing a pair must be >50%?

It looks like you are trying to answer a question different from that one asked in the problem text.
So analyzing the licence plates adding game you could for example be interested in how many cars Seth must see in order to have a winning chance of at least 10 % or 50% or 90%, which would all give different answers.

However, the problems asks for something else. Just imagine that Seth writes down each number plate until a win is reached (and doesn't add any car after winning). Whenever he repeats playing the game he always starts a new list. If he plays this game very often, you will see that the number of cars written down on the lists varies around some average. The problem is asking for this average, respective the expected number of cars on any list, to be more precise.

[brob26]

how is "expected to win" defined exactly? the chance of seeing a pair must be >50%?

Expanding on Animus' response, "expectation" here is defined in the statistical sense. The wikipedia page is a good place to start if you haven't encountered the concept previously.

I do remember it being a bit confusing when I was first learning, as "what one expects" in this statistical sense is not quite the same as what one might interpret from other use in English.