Project Euler Problem #100

Before I begin, I’d like to state that I will probably take a break from Project Euler for a little while. While writing these first 100 blog posts, I finally accomplished my goal of solving the first 100 problems on Project Euler. When I started, I never expected to make it this far. Writing a blog post per day really helped to give me a sense of purpose during my first semester of college. As a result, I would like to continue blogging about my problem-solving endeavors. However, I must confess that recently it has become more and more difficult to keep up with this schedule for solving Project Euler problems. Thus, in the future, I may discuss Project Euler from time to time, but it probably will not be daily, and it may not be in chronological order as many of the easier Project Euler problems are not at the start of the archives. With that being said, let’s get right into the math.

Problem #100 concerns discrete arrangements which will cause a probability to be equal to 50%. The question reads:

Project Euler Problem 100: Arranged probability
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.

My solution to this problem involves Pell Equations. Here is my solution:

Solution #1: Pell Equation Approach

Let the number of blue disks be b and let the total number of disks be t. We want to search for integer pairs (b,t) such that 2*b*(b-1) = t*(t-1). Writing this as 2b^2-2b+t-t^2 = 0 and solving for b, we get b = (2+sqrt(4+8t^2-8t))/4 = (1+sqrt(1+2t^2-2t))/2. Thus, it suffices to find values of t such that 2t^2-2t+1 = c^2 for some integer c. Solving for t, we get t = (2+sqrt(8c^2-4))/4 = (1+sqrt(2c^2-1))/2. Thus, it suffices to find values of c such that d^2-2c^2 = -1 for some integer d. The first three solutions to this are (1,1), (7,5), It follows that if (d,c) is a solution, (3*d+4*c,2*d+3*c) is the next solution. Thus, the integer solutions for c can be recursively generated, and each one can be translated to a distinct solution for the value of b. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Pell Equation Approach to Project Euler Problem #100
 '''
 
 import time
 
 def projectEulerProblemOneHundred(n):
     y = 7
     x = 5
     maxY = 2*n-1
     while(y<=maxY):
         tempX = 2*y+3*x
         tempY = 3*y+4*x
         y = tempY
         x = tempX
     return (x+1)/2
 
 start = time.time()
 print projectEulerProblemOneHundred(10**12)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 756872327473
 --- 1.12056732178e-05 seconds ---
 
 for input of 10**12.
 ''' 

And with that, we’re done. This is yet another example of the powers of Pell Equations. We wanted to find all solutions up to 1 trillion, and yet the program only took a hundredth of a millisecond to run.

Thanks for reading! See you tomorrow. As I mentioned above, I may or may not discuss Project Euler depending on whether I am stuck from this point onwards.