Problem 100

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

Don't post any spoilers
Comments, questions and clarifications about PE problems.
bramp
Posts: 4
Joined: Sun Sep 02, 2007 1:48 pm

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 * (b-1) / (t-1)
Where b is the blue discs, and t is the total number of discs.

Now I say that P(BB) = 1/2 and re-arrange 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
Posts: 1405
Joined: Sun Mar 26, 2006 5:30 am
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 64-bit 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.

bramp
Posts: 4
Joined: Sun Sep 02, 2007 1:48 pm

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.

rayfil
Posts: 1405
Joined: Sun Mar 26, 2006 5:30 am
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.
When you assume something, you risk being wrong half the time.

bramp
Posts: 4
Joined: Sun Sep 02, 2007 1:48 pm

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

bramp
Posts: 4
Joined: Sun Sep 02, 2007 1:48 pm

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

rayfil
Posts: 1405
Joined: Sun Mar 26, 2006 5:30 am
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.

yitzgale
Posts: 7
Joined: Mon Nov 12, 2007 10:10 am

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 Pell-like 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 well-known
sequence of solutions, none of them offer a proof that they are the
only ones. And there are indeed examples of Pell-like 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 Pell-like 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 11: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 x2 - D*y2 = 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 1012.
Il faut respecter la montagne -- c'est pourquoi les gypa&egrave;tes sont l&agrave;.

yitzgale
Posts: 7
Joined: Mon Nov 12, 2007 10:10 am

Re: Problem 100

since l = 1, x and y must be coprime
Well, l = -1, but yes.
for any solution x, y there is a convergent p/q of [radic]D, so that x/y = p/q
OK, good. But that statement does require some work to prove.

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
Posts: 3257
Joined: Sun Mar 05, 2006 4:49 pm
Location: Cheshire, England
Contact:

Re: Problem 100

yitzgale wrote:Well, l = -1,
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 x2 [minus] Dy2 = 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...

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 x2 [minus] Dy2 = 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:
(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

yitzgale
Posts: 7
Joined: Mon Nov 12, 2007 10:10 am

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

My view is that using the "Check" button on the PE web page
as part of a trial-and-error 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
Posts: 3257
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.

impudens simia et macrologus profundus fabulae

yitzgale
Posts: 7
Joined: Mon Nov 12, 2007 10:10 am

Re: Problem 100

OK, fair enough.

Thanks for your thoughtful replies, and thanks again for Project Euler!

Regards,
Yitz

daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11: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&egrave;tes sont l&agrave;.

Mr Banks
Posts: 1
Joined: Sun Apr 13, 2008 8:42 pm

Problem 100

If a box contains twenty-one 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 eighty-five blue discs and thirty-five 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.
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?

daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

Re: Problem 100 - Not Understanding

Consider all arrangements of NB blue discs and NR red discs where the probability that two randomly selected discs are both blue is exactly 50%. Ignore all those where NB+NR [le] 1012. 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&egrave;tes sont l&agrave;.

jaap
Posts: 550
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

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.

janardhanan
Posts: 3
Joined: Wed Jul 22, 2009 12:23 pm

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

hk