Loading...
Project Euler 100: Finding the number of blue discs for which there is 50% chance of taking two blue.
Project Euler 100 Problem Description
Project Euler 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 1012 = 1,000,000,000,000 discs in total, determine the number of blue discs that the box would contain.
Analysis
Given b=blue discs, n=total number of discs then the general equation is:
![\setlength\arraycolsep{2pt}\begin{array}{rl} \frac{b^2-b}{n^2-n} &= \textonehalf \\[6pt] \frac{2b^2-2b}{n^2-n} &= 1 \\[6pt] 2b^2-2b &= n^2-n \\[6pt] 2b^2-n^2-2b + n &= 0 \end{array}](https://s0.wp.com/latex.php?latex=+%5Csetlength%5Carraycolsep%7B2pt%7D%5Cbegin%7Barray%7D%7Brl%7D+%5Cfrac%7Bb%5E2-b%7D%7Bn%5E2-n%7D+%26%3D+%5Ctextonehalf+%5C%5C%5B6pt%5D+%5Cfrac%7B2b%5E2-2b%7D%7Bn%5E2-n%7D+%26%3D+1+%5C%5C%5B6pt%5D+2b%5E2-2b+%26%3D+n%5E2-n+%5C%5C%5B6pt%5D+2b%5E2-n%5E2-2b+%2B+n+%26%3D+0+%5Cend%7Barray%7D+&bg=ffffff&fg=000&s=1&c=20201002)
which is, in fact, a Diophantine Quadratic Equation and can be solved using a program provided on the following website: http://www.alpertron.com.ar/QUAD.HTM
Here is the input to the program for our equation:
[ 2] x2 +
[ 0] xy +
[-1] y2 +
[-2] x +
[ 1] y +
[ 0] = 0
Here is the output from the program:
2x2 – y2 – 2x + y = 0
X0 = 0
Y0 = 1
and also:
X0 = 1
Y0 = 1
Xn+1 = 3Xn + 2Yn – 2
Yn+1 = 4Xn + 3Yn – 3
From here we have two equations that can calculate b and n for each term in the series. Instead of starting at b=1, n=1 we start with the values in the problem description to save a few iterations; b=85, n=120. We continue this series until n>1012.
The equations are: blue disks = 3b + 2n – 2; n disks = 4b + 3n – 3 (also n = int(b/√2/2), but that’s another story).
Project Euler 100 Solution
Runs < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler 100 Solution Python 2.7 source.
Afterthoughts
-
No afterthoughts yet.
Yes it works, but can you please explain how you derived the two linear equations to continue the series. I do not understand where those came from.
Posted by Dave Doehman | October 23, 2009, 9:48 AMHi Dave, I rewrote the ‘analysis’ section with more information on how to find the equations. Let me know if this answers your question.
Posted by Mike | October 26, 2009, 2:18 AMYes very interesting. I did not know of a way to determine solutions that are restricted to integers. The math behind that website that generated the coefficents for the iterative equations is quite impressive and I can’t say I was able to follow it yet. The way these simple iterative equations pop out that gives the answer is almost magical. Very impressive.
Posted by Dave Doehman | October 27, 2009, 12:39 PM