This problem can be solved using basic probability, if you have the right insight.Ra1n wrote: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!!)
Problem 371
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.
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
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
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.
Re: Problem 371
Re: Problem 371
I am having issues with precision. Can somebody suggest me how to get over the problem of precision. I have tried logarithmantilogarithm to approximate but it does not give correct answer.
Re: Problem 371
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 bugfix which should be in release 3.0.)viv_ban wrote:I am having issues with precision. Can somebody suggest me how to get over the problem of precision. I have tried logarithmantilogarithm to approximate but it does not give correct answer.
Re: Problem 371
There are solutions in C++ using just double. So, you don't need anything more than that.
viv_ban wrote:I am having issues with precision. Can somebody suggest me how to get over the problem of precision. I have tried logarithmantilogarithm to approximate but it does not give correct answer.
puzzle is a euphemism for lack of clarity
 PurpleBlu3s
 Posts: 73
 Joined: Mon Sep 19, 2011 6:49 pm
Re: Problem 371
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
 Posts: 73
 Joined: Mon Sep 19, 2011 6:49 pm
Re: Problem 371
Can anyone confirm the probability of not having a win after seeing 10 plates is 0.95586930 (8 s.f.)?
Re: Problem 371
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.PurpleBlu3s wrote: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?
Re: Problem 371
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.)sivakd wrote: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 ...
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.
Re: Problem 371
There shouldn't be a period between "SET500 too" and "(as long" (I think).E.g. MIC012 and HAN988 is a win and RYU500 and SET500 too. (as long as he sees them in the same trip).

 Posts: 38
 Joined: Mon Aug 08, 2011 8:49 am
Re: Problem 371
I'm confused by seemingly contradicting statements in this thread.
On one hand
On one hand
On the otherthundre wrote:It's not a Bernoulli random variable because p depends on what happened in the previous trials.Nadando wrote:So why isn't this just a Bernoulli random variable with p = 999 / 1000000?
The last quote implies that the same license plate can be "redrawn" 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.rayfil wrote:Right. Even if it's XYZ500 and ABC500, or any other letter combinations.If so, for example, SET500 and SET500 will be a win. Right?
Re: Problem 371
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.
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.

 Posts: 6
 Joined: Mon Nov 02, 2015 12:31 am
Re: Problem 371
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?
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?

 Posts: 38
 Joined: Mon Aug 08, 2011 8:49 am
Re: Problem 371
Could someone go to this problem's closed forum and answer the question in my last post? Thanks.
 RishadanPort
 Posts: 78
 Joined: Mon Jun 10, 2013 7:31 am
Re: Problem 371
This probably has already been explained in this thread,  but I want clarity...
Is it possible for him to see the license plate SET500, and SET500 (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.
Is it possible for him to see the license plate SET500, and SET500 (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.
Rishada is the gateway to free trade—but the key will cost you.
 RishadanPort
 Posts: 78
 Joined: Mon Jun 10, 2013 7:31 am
Re: Problem 371
I'm not sure if this is the right place to ask this...
But lets suppose we see the numbers 1500 already.
Would the expected number of plates to see for a win be 2, or am I missing something.
But lets suppose we see the numbers 1500 already.
Would the expected number of plates to see for a win be 2, or am I missing something.
Rishada is the gateway to free trade—but the key will cost you.
 RishadanPort
 Posts: 78
 Joined: Mon Jun 10, 2013 7:31 am
Re: Problem 371
Nevermind I figured out why...
Indeed 500 is a magic number.
Indeed 500 is a magic number.
Rishada is the gateway to free trade—but the key will cost you.

 Posts: 8
 Joined: Fri Apr 27, 2018 7:17 pm
Re: Problem 371
how is "expected to win" defined exactly? the chance of seeing a pair must be >50%?
Re: Problem 371
It looks like you are trying to answer a question different from that one asked in the problem text.hamsterofdeath wrote: ↑Thu May 07, 2020 11:45 pmhow is "expected to win" defined exactly? the chance of seeing a pair must be >50%?
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.
Re: Problem 371
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.hamsterofdeath wrote: ↑Thu May 07, 2020 11:45 pmhow is "expected to win" defined exactly? the chance of seeing a pair must be >50%?
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.