Post date: Jan 20, 2019 1:34:1 AM
"Given a box containing blue and red discs, where the total number of discs in the box is over 10**12 and there is a 50% percentage of picking two discs and finding them both to be blue, what is the minimum number of blue discs."
Here we have a problem we can't solve right. But we can solve it.
The basic equation is such:
(blue/total) * ((blue-1)/(total-1)) = (blue * (blue-1))/(total * (total-1)) = (blue**2 - blue)/(total**2 -total) = 0.5
(2*blue**2 - 2*blue)/(total**2 -total) = 1
2*blue**2 - 2*blue - total**2 + total = 0
This is a Diophantine Quadratic Equation. I had to go to Google for this one because it's way beyond my math knowledge, and apparently there is no universally correct algorithm. Project Euler wants me to solve an unsolved maths problem to celebrate problem 100 but, well, ha ha.
In this case, we can go to an algorithm from a java program by Dario Alpern, which is what every solution I find goes to. Reports are that this can't solve every case. It hangs or produces incorrect results. But in this case, it works. The formulas it uses are these:
X(n+1) = 3x(n) + 2y(n) - 2
Y(n+1) = 4x(n) + 3y(n) - 3
Well that's something I can use. It's iterative, so I just loop until y is over 1 trillion. I didn't really solve this problem, but I did successfully implement it. Happy 100th Euler.
This isn't the last Project Euler problem, but I think it will be the last one I do. It's a nice round number, and there hasn't been a really interesting problem in a while, so I think it's a good stopping point. I'm spending more time on front-end coding these days anyway (though that's not necessarily a good thing ... there's a glut of front-end coders so if I have to take over, it means things are going badly).
declare @blue bigint = 15, @blue2 bigint
declare @total bigint, @total2 bigint
while (@total < 1000000000000)
begin
select @blue2 = 3 * @blue + 2 * @total - 2, @total2 = 4 * @blue + 3 * @total - 3
select @blue = @blue, @total = @total2
end
select @blue