Project Euler Problem 100

Statement

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.

Solution

We start with this equation:
b = blue disks
n = total disks

(1)
\begin{eqnarray} \frac{b}{n} * \frac{b-1}{n-1} & = & \frac{1}{2}\\ \frac{b * (b-1)}{n * (n-1)} & = & \frac{1}{2}\\ \frac{b^2 -b}{n^2 -n} & = & \frac{1}{2}\\ 2 \frac{b^2 -b}{n^2 -n} & = & 1\\ 2 (b^2 -b) & = & n^2 - n\\ 2b^2 -2b -n^2 +n & = & 0 \end{eqnarray}

We arrived to a Quadratic Diophantine Equation, to solve it I used this webpage: http://www.alpertron.com.ar/QUAD.HTM

There we complete the values using x as b and y as n.

The result we have is that there are 2 series, built the same way with different starters. The function for creating the series is:
$B_{n+1} = PB_n + QN_n + K$

$N_{n+1} = RB_n + SN_n + L$

where:
P = 3
Q = 2
K = -2
R = 4
S = 3
L = -3

We don't care about the starters cause we have values from the sequence: B = 15 and N = 21. Basically I wrote a python program that generates the sequence until N > 1012.

if __name__ == '__main__':
    p = 3
    q = 2
    k = -2
    r = 4
    s = 3
    l = -3
 
    b = 15
    n = 21
    while n < 10 ** 12:
        b, n = (p * b + q * n + k, r * b + s * n + l)
    print("The result is:", b)

The Python file is available for download here.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License