// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (11 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 100 Solution

Project Euler 100 Solution

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}

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.
download arrowUse this link to get the Project Euler 100 Solution Python 2.7 source.

Afterthoughts

    No afterthoughts yet.
Project Euler 100 Solution last updated

Discussion

3 Responses to “Project Euler 100 Solution”

  1. 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 AM
    • Hi 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 AM
      • Yes 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

Post a comment