Problem 100
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.
Project Euler Problem 100  I'm stuck :(
Hi,
I'm Andrew, and so far I've been cruising through the puzzles on project euler, so I've started to complete the puzzles in a random order and I've got stuck on problem 100
"Finding the number of blue discs for which there is 50% chance of taking two blue."
Now I don't know how much maths/answers I should put on this forum, but the approach I've taken so far is to work out the equation
P(BB) = b / t * (b1) / (t1)
Where b is the blue discs, and t is the total number of discs.
Now I say that P(BB) = 1/2 and rearrange to make b the subject , and thus I've coded something to loop from t=10^12 until I find a integer solution for b... The problem comes that I can quickly find solutions for b, but none of the ones I enter are valid, yet I've double checked.
So either I'm solving the problem in the wrong way, or I've missed the correct solution.
Thanks for any help/comment/feedback
Andrew
I'm Andrew, and so far I've been cruising through the puzzles on project euler, so I've started to complete the puzzles in a random order and I've got stuck on problem 100
"Finding the number of blue discs for which there is 50% chance of taking two blue."
Now I don't know how much maths/answers I should put on this forum, but the approach I've taken so far is to work out the equation
P(BB) = b / t * (b1) / (t1)
Where b is the blue discs, and t is the total number of discs.
Now I say that P(BB) = 1/2 and rearrange to make b the subject , and thus I've coded something to loop from t=10^12 until I find a integer solution for b... The problem comes that I can quickly find solutions for b, but none of the ones I enter are valid, yet I've double checked.
So either I'm solving the problem in the wrong way, or I've missed the correct solution.
Thanks for any help/comment/feedback
Andrew
 rayfil
 Administrator
 Posts: 1403
 Joined: Sun Mar 26, 2006 4:30 am
 Location: Ontario, Canada
 Contact:
Re: Project Euler Problem 100  I'm stuck :(
The only aspect I'm going to comment on are potential pitfalls, not knowing which programming language you use, nor the adequacy of your rearranged equation, nor the data types you use.
 The numbers being at the levels of 10^12, multiplying two such numbers as integers would exceed the range of even 64bit integers. Using integer data types for such a multiplication may not raise internal error flags in your program but would definitely produce erroneous results.
 If you perform a division using integer data types, the result is either truncated or rounded if the numerator is not an exact multiple of the denominator. Using such results in subsequent computations may introduce those rounding errors elsewhere. Ex. 10/3=3, 6x3=18, but 6x10/3=20.
 The numbers being at the levels of 10^12, multiplying two such numbers as integers would exceed the range of even 64bit integers. Using integer data types for such a multiplication may not raise internal error flags in your program but would definitely produce erroneous results.
 If you perform a division using integer data types, the result is either truncated or rounded if the numerator is not an exact multiple of the denominator. Using such results in subsequent computations may introduce those rounding errors elsewhere. Ex. 10/3=3, 6x3=18, but 6x10/3=20.
When you assume something, you risk being wrong half the time.
Re: Project Euler Problem 100  I'm stuck :(
thanks rayfil...
I had considered overflowing of my variables, but the values should never go much higher than 10^12. Originally I was using floats in PHP, and then I coded the same app in Matlab, both of which gave me the same answer, which apparently is wrong.
The thing is I can check the answer is valid by plugging it back into my P(BB) formula and checking the result is 1/2...
So I think I've either miss understood the question, or am going about it in the wrong way.
I had considered overflowing of my variables, but the values should never go much higher than 10^12. Originally I was using floats in PHP, and then I coded the same app in Matlab, both of which gave me the same answer, which apparently is wrong.
The thing is I can check the answer is valid by plugging it back into my P(BB) formula and checking the result is 1/2...
So I think I've either miss understood the question, or am going about it in the wrong way.
 rayfil
 Administrator
 Posts: 1403
 Joined: Sun Mar 26, 2006 4:30 am
 Location: Ontario, Canada
 Contact:
Re: Project Euler Problem 100  I'm stuck :(
It must also be taken into consideration that floats are limited to the following accuracy:
single precision  24 bits
double precision  53 bits
extended double precision  64 bits
Although the range of floats can be considerable, rounding errors are as troublesome as when using integers.
single precision  24 bits
double precision  53 bits
extended double precision  64 bits
Although the range of floats can be considerable, rounding errors are as troublesome as when using integers.
When you assume something, you risk being wrong half the time.
Re: Project Euler Problem 100  I'm stuck :(
Ok,
So I've recoded my solution using a arbitrary precision math library, and its not finding the same solution. In fact it's not finding any solution yet So maybe this is the problem.
Anyway my arbitrary precision math library solution is taking far more than a minute to run, and as I'm trying to keep all my solutions to be calculated to under a minute I might try a different approach.
thanks
So I've recoded my solution using a arbitrary precision math library, and its not finding the same solution. In fact it's not finding any solution yet So maybe this is the problem.
Anyway my arbitrary precision math library solution is taking far more than a minute to run, and as I'm trying to keep all my solutions to be calculated to under a minute I might try a different approach.
thanks
Re: Project Euler Problem 100  I'm stuck :(
Ok so my original problem was that my floating point variables weren't precise enough, thus they were finding false positives, which also validated as positives .
I have now solved the solution using a variant of my original approach.
thanks
I have now solved the solution using a variant of my original approach.
thanks
 rayfil
 Administrator
 Posts: 1403
 Joined: Sun Mar 26, 2006 4:30 am
 Location: Ontario, Canada
 Contact:
Re: Project Euler Problem 100  I'm stuck :(
Glad to have helped a little without having given away anything. My solution is described at the top of the 2nd page of the forum for Problem 100.
When you assume something, you risk being wrong half the time.
Problem 100
As stated, Problem 100 requires finding the _first_ solution such that
the total number of discs is >10^12. Looking at the forum, _no_one_
has actually solved this problem yet. Many people  including myself 
have found an example with >10^12 discs, using the usual kinds of
techniques for Pelllike equations. But to _prove_ that this is the
first such solution appears to be very hard. Brute force does
not seem practical for this, either, since the apparent first
solution (which you accept as the correct answer) has many more
than 10^12 discs. Browsing the web via Google, I find that while
there are a number of sites that show how to generate the wellknown
sequence of solutions, none of them offer a proof that they are the
only ones. And there are indeed examples of Pelllike equations
that have more than one sequence of solutions (see the Wolfram
site).
Someone on Wikipedia posted  without citation, unfortunately 
the comment that Gauss had two possible classifications of
the solutions to Pelllike equations, and that choosing between
them is equivalent to deciding the Riemann hypothesis.
Am I (and everyone else that has posted to the forum so far)
missing something? Is there some easy proof for this
admittedly simple special case?
Perhaps you should add a comment to the statement of this
problem stating that you may assume there is a unique
solution between 10^12 and 5*10^12. If that is indeed true.
Thanks,
Yitz
the total number of discs is >10^12. Looking at the forum, _no_one_
has actually solved this problem yet. Many people  including myself 
have found an example with >10^12 discs, using the usual kinds of
techniques for Pelllike equations. But to _prove_ that this is the
first such solution appears to be very hard. Brute force does
not seem practical for this, either, since the apparent first
solution (which you accept as the correct answer) has many more
than 10^12 discs. Browsing the web via Google, I find that while
there are a number of sites that show how to generate the wellknown
sequence of solutions, none of them offer a proof that they are the
only ones. And there are indeed examples of Pelllike equations
that have more than one sequence of solutions (see the Wolfram
site).
Someone on Wikipedia posted  without citation, unfortunately 
the comment that Gauss had two possible classifications of
the solutions to Pelllike equations, and that choosing between
them is equivalent to deciding the Riemann hypothesis.
Am I (and everyone else that has posted to the forum so far)
missing something? Is there some easy proof for this
admittedly simple special case?
Perhaps you should add a comment to the statement of this
problem stating that you may assume there is a unique
solution between 10^12 and 5*10^12. If that is indeed true.
Thanks,
Yitz
 daniel.is.fischer
 Posts: 2400
 Joined: Sun Sep 02, 2007 10:15 pm
 Location: Bremen, Germany
Re: Problem 100
There is a not too difficult proof using the theory of continued fractions.
Whenever you have an equation x^{2}  D*y^{2} = l, with abs(l) < [radic]D, for any solution x, y there is a convergent p/q of [radic]D, so that x/y = p/q. In this case, since l = 1, x and y must be coprime, hence x/y is reduced, thus a convergent of [radic]D. Now the convergents of [radic]D are easily determined and the accepted solution is proven to be the smallest above 10^{12}.
Whenever you have an equation x^{2}  D*y^{2} = l, with abs(l) < [radic]D, for any solution x, y there is a convergent p/q of [radic]D, so that x/y = p/q. In this case, since l = 1, x and y must be coprime, hence x/y is reduced, thus a convergent of [radic]D. Now the convergents of [radic]D are easily determined and the accepted solution is proven to be the smallest above 10^{12}.
Il faut respecter la montagne  c'est pourquoi les gypaètes sont là.
Re: Problem 100
Well, l = 1, but yes.since l = 1, x and y must be coprime
OK, good. But that statement does require some work to prove.for any solution x, y there is a convergent p/q of [radic]D, so that x/y = p/q
I don't think that the intention is that it should be a requirement to
find that proof in order to solve the problem. So I would still recommend adding
some kind of comment that allows people to assume that the solution is
unique once they find it.
Thanks,
Yitz
 euler
 Administrator
 Posts: 3139
 Joined: Sun Mar 05, 2006 4:49 pm
 Location: Cheshire, England
 Contact:
Re: Problem 100
Actually, Daniel was quite correct. It is possible to state this problem in the form he gave and is always preferable if possible. The reason he did this is that a solution always exists for x^{2} [minus] Dy^{2} = 1, whereas when the RHS is 1 there may be no solution (in fact it exists if and only if the period length of the continued fraction is odd). Now the tricky bit...yitzgale wrote:Well, l = 1,
It is true that every solution of the Pell equation is a convergent, x/y, of the continued fraction of [radic]D, but the converse theorem is that every convergent, x/y, is a solution to the equation x^{2} [minus] Dy^{2} = N, where N is not necessarily equal to 1, but N < 1 +2[radic]D. However, it can be proved that N will eventually be equal to 1 and it can also be shown that infinitely many will equal 1.
I prove that here:
Radical Convergence
(Note that the iterative formula I use in the proof does not provide every solution to the Diophantine equation, it only shows that infinitely many solutions exist.)
In general, blindly using convergents is not safe, but for Project Euler problems we carefully pick parameters to ensure accessibility to those without the mathematics. And for this problem, once you have the correct Pell equation alternate convergents solve the equation.
However, if you are interested... the general approach that mathematicians use is to determine the minimal solution using the convergents of the continued fraction for [radic]D, (x1,y1); that is, we know that one solution to the original Pell (with RHS = 1) definitely exists and eventually it will turn up among the convergents. Then it can be proved that EVERY solution to the Pell equation is given by x + y[radic]D = +(x1 + y1[radic]D)^{n} and so a simple iterative model can be used to churn them out sequentially.
You ask an interesting question, but I feel that adding an additional disclaimer would muddy the problem wording unnecessarily.
impudens simia et macrologus profundus fabulae
Re: Problem 100
Thanks for the nice stuff on Pell equations, both you and Daniel.
I guess my focus here, though, is really more on the philosophy
of Project Euler than on the math. You have verified what I surmised 
that there is no really elementary way of verifying that a
solution to this problem is the first one having more than 10^{12} discs.
My view is that using the "Check" button on the PE web page
as part of a trialanderror process to solve a problem is not
ideal. I try very hard not to "cheat" and press the "Check"
button until I feel that I have really solved the problem,
and proven that my answer is correct.
So I was disappointed when I realized that this would not
be possible with Problem 100. Though learning the
theory is nice, of course.
Are there other problems that cannot be fully solved
without searching the web or textbooks?
Thanks for all of your great work on Project Euler!
Regards,
Yitz
I guess my focus here, though, is really more on the philosophy
of Project Euler than on the math. You have verified what I surmised 
that there is no really elementary way of verifying that a
solution to this problem is the first one having more than 10^{12} discs.
My view is that using the "Check" button on the PE web page
as part of a trialanderror process to solve a problem is not
ideal. I try very hard not to "cheat" and press the "Check"
button until I feel that I have really solved the problem,
and proven that my answer is correct.
So I was disappointed when I realized that this would not
be possible with Problem 100. Though learning the
theory is nice, of course.
Are there other problems that cannot be fully solved
without searching the web or textbooks?
Thanks for all of your great work on Project Euler!
Regards,
Yitz
 euler
 Administrator
 Posts: 3139
 Joined: Sun Mar 05, 2006 4:49 pm
 Location: Cheshire, England
 Contact:
Re: Problem 100
It is certainly commendable that you are so determined to obtain a comprehensive understanding of every problem. However, not everyone thinks the same way and people do Project Euler problems for very different reasons. I don't think there is any "cheating" going on for someone who gets to the point of obtaining the answer to, say, problem 100, even if they don't fully grasp the mathematics behind it. You will often see people like yourself in the main forum saying things like, "I used the following approach, but I have no idea why it works." I would say that if you've reached a point where you know the answer is ___, and assuming you wish to go deeper, you can then begin research proper with a level of confidence in your ideas; the hope from our perspective is that you've actively pursued enough mathematics in the "right" direction to make headway with further research. Our goal is never to present a problem which cannot be solved unless you've read an entire library of Number Theory books. That is, we hope that the level of difficulty lies somewhere between not being able to guess completely and not requiring a master's degree in mathematics.
With reference to your question: are there other problems requiring such extensive background to be absolutely certain that the solution is optimum? Yes, indeed. But as I mentioned you will never be completely denied access, nor will you simply be able to get to the answer for wrong reason. Also bear in mind that although absolute certainty that the optimum is the agreed answer may not be immediately verifiable by some people, the answer itself has been completely verified by a team of talented mathematicians and backed up by rigorous proofs; we never publish problems for which we cannot determine the solution by either analysis or an exhaustive search of the only possible cases.
And I'm glad you're enjoying the problems. Long may it continue.
With reference to your question: are there other problems requiring such extensive background to be absolutely certain that the solution is optimum? Yes, indeed. But as I mentioned you will never be completely denied access, nor will you simply be able to get to the answer for wrong reason. Also bear in mind that although absolute certainty that the optimum is the agreed answer may not be immediately verifiable by some people, the answer itself has been completely verified by a team of talented mathematicians and backed up by rigorous proofs; we never publish problems for which we cannot determine the solution by either analysis or an exhaustive search of the only possible cases.
And I'm glad you're enjoying the problems. Long may it continue.
impudens simia et macrologus profundus fabulae
Re: Problem 100
OK, fair enough.
Thanks for your thoughtful replies, and thanks again for Project Euler!
Regards,
Yitz
Thanks for your thoughtful replies, and thanks again for Project Euler!
Regards,
Yitz
 daniel.is.fischer
 Posts: 2400
 Joined: Sun Sep 02, 2007 10:15 pm
 Location: Bremen, Germany
Re: Problem 100
And when you're not sure that you've got the right answer, but are optimistic, try it, and if it's right, you can probably learn in the problem thread why it's the answer
Il faut respecter la montagne  c'est pourquoi les gypaètes sont là.
Problem 100
I understand the first two bits, but the last bit I don't understand.. would it be exactly the same situation as the first one, just replace the number 21 with 10^12 and 20 with 12^12 1 and find the number to replace 15?If a box contains twentyone coloured discs, composed of fifteen blue discs and six red discs, and two discs were taken at random, it can be seen that the probability of taking two blue discs, P(BB) = (15/21)Ã—(14/20) = 1/2.
The next such arrangement, for which there is exactly 50% chance of taking two blue discs at random, is a box containing eightyfive blue discs and thirtyfive red discs.
By finding the first arrangement to contain over 10^12 = 1,000,000,000,000 discs in total, determine the number of blue discs that the box would contain.
 daniel.is.fischer
 Posts: 2400
 Joined: Sun Sep 02, 2007 10:15 pm
 Location: Bremen, Germany
Re: Problem 100  Not Understanding
Consider all arrangements of N_{B} blue discs and N_{R} red discs where the probability that two randomly selected discs are both blue is exactly 50%. Ignore all those where N_{B}+N_{R} [le] 10^{12}. Among the remaining, find the one with the smallest total number of discs in it. The answer is the number of blue discs in that arrangement.
Il faut respecter la montagne  c'est pourquoi les gypaètes sont là.
Re: Problem 100  Not Understanding
I had a bit of trouble understanding this one too on first reading. Most probability problems ask for a probability to be "at least 1/2", "at most 1/2", or something similar. This one the probability has to be exactly 1/2, no more, no less. That changes the nature of the problem completely.
_{Jaap's Puzzle Page}

 Posts: 3
 Joined: Wed Jul 22, 2009 11:23 am
Re: Problem 100
I dont know where to post this, so I am posting here.
Please tell me why the below given numbers are NOT the correct answer. These numbers also satisfies the Problem 100's condition.
Number of Blue disc : 707106788769
Total number of disc : 1000000010723
Please tell me why the below given numbers are NOT the correct answer. These numbers also satisfies the Problem 100's condition.
Number of Blue disc : 707106788769
Total number of disc : 1000000010723
Re: Problem 100
The probability is not exactly 1/2.
I think you are using floating point aritmetic with double precision....
With 80 bit precision your numbers give: 0.50000000000000002
I think you are using floating point aritmetic with double precision....
With 80 bit precision your numbers give: 0.50000000000000002