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.
thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

Re: Problem 371

Post by thundre »

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!!)
This problem can be solved using basic probability, if you have the right insight.
Image

viv_ban
Posts: 23
Joined: Mon May 26, 2008 3:09 pm

Re: Problem 371

Post by 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
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

Re: Problem 371

Post by thundre »

viv_ban wrote: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.)
Image

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

Re: Problem 371

Post by sivakd »

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 logarithm-antilogarithm to approximate but it does not give correct answer.
Image
puzzle is a euphemism for lack of clarity

User avatar
PurpleBlu3s
Posts: 73
Joined: Mon Sep 19, 2011 6:49 pm

Re: Problem 371

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

User avatar
PurpleBlu3s
Posts: 73
Joined: Mon Sep 19, 2011 6:49 pm

Re: Problem 371

Post by PurpleBlu3s »

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

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

Re: Problem 371

Post by thundre »

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

gnome
Posts: 3
Joined: Sat Jul 28, 2012 12:55 pm

Re: Problem 371

Post by gnome »

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 ith 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
Posts: 8
Joined: Thu Nov 15, 2012 8:34 am

Re: Problem 371

Post by thkang »

500 is a curious number..

User avatar
jake223
Posts: 57
Joined: Mon Apr 25, 2011 5:15 am
Location: USA
Contact:

Re: Problem 371

Post by 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).
Image

oleglyamin
Posts: 38
Joined: Mon Aug 08, 2011 8:49 am

Re: Problem 371

Post by oleglyamin »

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

On one hand
thundre wrote:
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.
On the other
rayfil wrote:
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
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

Re: Problem 371

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

demongolem
Posts: 6
Joined: Mon Nov 02, 2015 12:31 am

Re: Problem 371

Post by 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
Posts: 38
Joined: Mon Aug 08, 2011 8:49 am

Re: Problem 371

Post by oleglyamin »

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

User avatar
RishadanPort
Posts: 78
Joined: Mon Jun 10, 2013 7:31 am

Re: Problem 371

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

Rishada is the gateway to free trade—but the key will cost you.

User avatar
RishadanPort
Posts: 78
Joined: Mon Jun 10, 2013 7:31 am

Re: Problem 371

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

Rishada is the gateway to free trade—but the key will cost you.

User avatar
RishadanPort
Posts: 78
Joined: Mon Jun 10, 2013 7:31 am

Re: Problem 371

Post by RishadanPort »

Nevermind I figured out why...

Indeed 500 is a magic number.
Image

Rishada is the gateway to free trade—but the key will cost you.

hamsterofdeath
Posts: 8
Joined: Fri Apr 27, 2018 7:17 pm

Re: Problem 371

Post by hamsterofdeath »

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

User avatar
Animus
Administrator
Posts: 1849
Joined: Sat Aug 16, 2014 1:23 pm

Re: Problem 371

Post by Animus »

hamsterofdeath wrote:
Thu May 07, 2020 11:45 pm
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
Posts: 5
Joined: Thu Nov 22, 2018 3:48 am

Re: Problem 371

Post by brob26 »

hamsterofdeath wrote:
Thu May 07, 2020 11:45 pm
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.
Image

Post Reply