Project Euler Forum

Are the letters restricted to uppercase?

Does Seth reckon in his own license plate? For example, suppose Seth's license plate is SET-001, when he saw CAT-999, is this a win?

greedp wrote:Are the letters restricted to uppercase?

Does that matter?

Does Seth reckon in his own license plate? For example, suppose Seth's license plate is SET-001, when he saw CAT-999, is this a win?

Do you see your licence plate when driving?

Is 000 valid?

LarryBlake wrote:Is 000 valid?

000 is a valid license plate number.

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

I was thinking that this would be Geometric, but that doesn't seem to be the case either for one reason or another.

Nadando wrote: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.

I am thoroughly confused by the note and also the update by hk above. Is it valid to see the same license plate multiple times (as it can happen in real life on the high-ways )? If so, for example, SET-500 and SET-500 will be a win. Right?

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.

From the problem description,

expected number of plates he needs to see for a win

As hk implied, you never see your own plate while on the road. (And, even if you did, it would still be one of the expected number if you consider it as a random 3-digit plate.)

SET-500 and SET-500 is same car twice
XYZ-500 and ABC-500 is two separate cars

By saying "you consider it as a random 3-digit plate" are you implying to ignore the letters? Which is related to hk's comment "Does that matter?" for considering upper/lowercase letters. Ignoring letters will alter the distribution.

SET-500 and SET-500 is same car twice

I have to admit that you may have a point there IF they are both Oregon plates. And in heavy traffic, you could see it numerous times, specially if it's on the car in front of you. But, with a bit of imagination, numerous other scenarios could be elaborated (albeit not in this thread).

From the problem statement,

Whenever the numbers of two licence plates seen on his trip

maybe the two should have been underlined and then explained/qualified in considerably more detail.

Any suggestion?

rayfil wrote:

SET-500 and SET-500 is same car twice

I have to admit that you may have a point there IF they are both Oregon plates. And in heavy traffic, you could see it numerous times, specially if it's on the car in front of you. But, with a bit of imagination, numerous other scenarios could be elaborated (albeit not in this thread).

From the problem statement,

Whenever the numbers of two licence plates seen on his trip

maybe the two should have been underlined and then explained/qualified in considerably more detail.

Any suggestion?

Yes.
Add the note:

I fear that explaining in considerable more detail makes an otherwise nice problem almost unreadable.

sivakd wrote:SET-500 and SET-500 is same car twice
XYZ-500 and ABC-500 is two separate cars

By saying "you consider it as a random 3-digit plate" are you implying to ignore the letters? Which is related to hk's comment "Does that matter?" for considering upper/lowercase letters. Ignoring letters will alter the distribution.

The note: tells you exactly to ignore the letters and also to ignore other so called "literate" attempts to make the problem more difficult than was meant.

hk wrote:

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

tells you exactly to ignore the letters and also to ignore other so called "literate" attempts to make the problem more difficult than was meant.

I think the word "may" should be changed to "must" or "should". It's imperative to get the answer, unlike (for example) problem 177 which states: which I take as an optional suggestion.

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

Seeing the troubles some people have had I changed the note into This is according to the same strategy as used in Problem 317 (View Problem) where is stated : I doubt that firecrackers can be launched in vacuum and the gravitational field of the earth (or whichever celestial body) is far from uniform.

Doing as if there are exactly 26^3*1000 cars moving around is as doubtful an assumption as nobody can assure that exactly all licence plates have been handed out and that e.g. some that were handed out long ago aren't in use any more.

States definitely use nonrandom methods to generate the license plates; for example, letter combinations that might be offensive or politically charged are suppressed.

Can someone explain the best way to go about a problem like this? Is this more paper-and-pencil than it is programming? Obviously a simple simulation would take way to long to get the accuracy required, right? There are plenty more of these "simulation"-type problems on ProjectEuler where, given enough time, a simulation would work (I think) although that clearly isn't the most efficient way of doing it. What principals are at play here?

Paper & Pencil can be used to come up with some formulas but you would need a computer to crunch the numbers. At least an Excel would come handy. Writing simulation usually helps validate whether the formulas are in the right direction or not as it did in my case. I wouldn't recommend running simulation for a long time till you arrive at the desired precision or close to it and testing out a few values. That would defeat the purpose of solving these type of problems.

Paper & Pencil can be used to come up with some formulas but you would need a computer to crunch the numbers. At least an Excel would come handy. Writing simulation usually helps validate whether the formulas are in the right direction or not as it did in my case. I wouldn't recommend running simulation for a long time till you arrive at the desired precision or close to it and testing out a few values. That would defeat the purpose of solving these type of problems.

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