Problem 371

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
greedp
Posts: 6
Joined: Sat Sep 24, 2011 12:38 pm

Problem 371

Post by greedp »

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?
Image

User avatar
hk
Administrator
Posts: 10817
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Problem 371

Post by hk »

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

LarryBlake
Posts: 100
Joined: Sat Aug 29, 2009 8:49 pm

Re: Problem 371

Post by LarryBlake »

Is 000 valid?
Image

thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

Re: Problem 371

Post by thundre »

LarryBlake wrote:Is 000 valid?
000 is a valid license plate number.
Image

Nadando
Posts: 2
Joined: Thu Mar 31, 2011 4:42 am

Re: Problem 371

Post by Nadando »

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

ParadiceCity9
Posts: 15
Joined: Sat Dec 17, 2011 7:15 pm
Location: Charlottesville, Virginia

Re: Problem 371

Post by ParadiceCity9 »

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

thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

Re: Problem 371

Post by thundre »

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

sivakd
Posts: 217
Joined: Fri Jul 17, 2009 9:37 am
Location: California, USA
Contact:

Re: Problem 371

Post by sivakd »

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?
Image
puzzle is a euphemism for lack of clarity

User avatar
rayfil
Administrator
Posts: 1405
Joined: Sun Mar 26, 2006 5:30 am
Location: Quebec, Canada
Contact:

Re: Problem 371

Post by rayfil »

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.)
When you assume something, you risk being wrong half the time.

sivakd
Posts: 217
Joined: Fri Jul 17, 2009 9:37 am
Location: California, USA
Contact:

Re: Problem 371

Post by sivakd »

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.
Image
puzzle is a euphemism for lack of clarity

User avatar
rayfil
Administrator
Posts: 1405
Joined: Sun Mar 26, 2006 5:30 am
Location: Quebec, Canada
Contact:

Re: Problem 371

Post by rayfil »

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. 8-) 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?
When you assume something, you risk being wrong half the time.

User avatar
hk
Administrator
Posts: 10817
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Problem 371

Post by hk »

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

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

User avatar
hk
Administrator
Posts: 10817
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Problem 371

Post by hk »

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

thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

Re: Problem 371

Post by thundre »

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:
Note: In your calculations you may assume that a calculated angle is integral if it is within a tolerance of 10-9 of an integer value.
which I take as an optional suggestion.
Image

sivakd
Posts: 217
Joined: Fri Jul 17, 2009 9:37 am
Location: California, USA
Contact:

Re: Problem 371

Post by sivakd »

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 ith car seen". It may be same as the Note: provided in the problem, but for people who have difficulty understanding the note ...
Image
puzzle is a euphemism for lack of clarity

User avatar
hk
Administrator
Posts: 10817
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Problem 371

Post by hk »

Seeing the troubles some people have had I changed the note into
We assume that each licence plate seen is equally likely to have any three digit number on it.
This is according to the same strategy as used in Problem 317 (View Problem) where is stated :
We assume that the fragments move without air resistance...
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.
Image

User avatar
mvaneerde
Posts: 4
Joined: Mon Dec 05, 2011 12:06 am
Location: Redmond, WA
Contact:

Re: Problem 371

Post by mvaneerde »

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

Ra1n
Posts: 2
Joined: Sat Dec 11, 2010 4:08 am

Re: Problem 371

Post by Ra1n »

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?
Image

sivakd
Posts: 217
Joined: Fri Jul 17, 2009 9:37 am
Location: California, USA
Contact:

Re: Problem 371

Post by sivakd »

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.
Image
puzzle is a euphemism for lack of clarity

Ra1n
Posts: 2
Joined: Sat Dec 11, 2010 4:08 am

Re: Problem 371

Post by Ra1n »

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

Post Reply