Project Euler - problem 100
Back to the hopeless examples of probabilities from school. In a bag there are 15 black balls and six white ones. Project Euler talks about discs, math-teachers has always used balls as examples, and they where always white and black. So I’ll stick with that.
It you draw two balls from the bag, there is a 50/50 chance of drawing 2 black balls:
(15/21)*(14/20)
I’m told that the next set of balls in the bag with that property, is 85 black balls and 35 white ones: (85/120)
(85/120)*(84/119)
Find the mix of black and white balls, that gives a probability of 50/50 of drawing 2 black balls, given that there should be more than 10¹² = 1000000000000 balls in the rather large bag.
That should be straight-forward. Lets call the number of black balls b and the number of white balls w. And lets define the total number of balls in the back as n=w+b The probability of drawing two black balls is:
(b/n)((b-1)/(n-1)) = ½
n = w + b > 10¹²
Two equations with two unknowns. The probability can be rearranged:
(b/n)((b-1)/(n-1)) = ½ <=>
b(b-1) / n(n-1) = ½ <=>
(b² - b) / (n² - n) = ½ <=>
b² - b = ½(n² - n) <=>
2b² - 2b = n² - n <=>
2b² - 2b - n² + n = 0
Hm. Maybe it is not that simple after all. First of all I don’t know if n is 100000000000 or 100000000001. That actually makes a pretty big difference:
10000000000012 - 10000000000002
Second of all, I need to find integer solutions. An analytical solution might not give integer results. And I can’t have one third of a ball in the bag.
Googling “finding integer solutions to equations” give, as the first result, a link to the wikipedia article on “Diophantine equations”. Which apparently are equations that should have integer solutions.
All right, a couple of the problems I’ve tackled earlier, and quite a lot of Project Euler problems I’ve given up on appears to be about solving these Diophantine equations.
So. Nice. The last link of the wikipedia page is to https://www.alpertron.com.ar/QUAD.HTM. I should probably read up on the methods. But that will have to wait.
The point is, that this Diophantine equation can be solved by:
bn+1 = 3bn + 2nn -2
nn+1 = 4bn + 3nn -3
The idea is that we have a solution (bn, nn). And these two equations allows us to calculate the next solution, (bn+1, nn+1)
Lets try that, we was given that (15,21) was a solution. The next should be (85,120). Do we get that?
b <- 15 n <- 21 b_n <- 3b + 2n -2 n_n <- 4b + 3n -3 print(paste(b_n, n_n, sep=“,”))
Qap’la, it works. Nice. Now I just need to run through this until nn+1 gets above 10¹².
b <- 15 n <- 21 while(n<10**12){ b_n <- 3b + 2n -2 n_n <- 4b + 3n -3 b <- b_n n <- n_n } answer <- b
Lessons learned:
Solving Diophantine equations is at the heart of a lot of these problems. I’ve learned a new tools to handle them! If you want to subscript stuff in RMarkdown, you place a ~ on each side of what you want subscripted.
Other stuff to note: Maybe it is time someone wrote a new solver for Diophantine equations. The one I found is 19 years old. Something to do in Shiny perhaps?