Project Euler 100: Finding the number of blue discs for which there is 50% chance of taking two blue.
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.
Given b=blue discs, n=total number of discs then the general equation is:
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
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 SolutionRuns < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler 100 Solution Python 2.7 source.
AnswerSlowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
No afterthoughts yet.