#!/usr/bin/env ruby
# encoding: UTF-8
# Solution to Project Euler problem 100
# Author: David J. Oftedal.
# Find the first arrangement of more than 10¹² red and blue discs for
# which the probability of picking two blue discs at random would be 50%.
if $0 == __FILE__
last_pile_size = 1
pile_size = 2
loop do
# Picking up a disc decreases the size of the pile by 1.
denominator = pile_size*(pile_size-1)
# The probability of picking blue must be some number a*(a-1)
# divided by the pile size. Find the probability closest to 50%.
blue = ((denominator/2.0)**0.5).ceil.to_i
numerator = blue*(blue-1)
if numerator * 2 == denominator
if pile_size > 1000000000000
puts "The first arrangement over 10¹² with a 50% probability of two blues is " << blue.to_s << " blue and " << (pile_size-blue).to_s << " red."
exit(0)
end
multiplier = pile_size / last_pile_size
last_pile_size = pile_size.to_f
# Skip the same interval as we skipped to get here.
pile_size = (pile_size*multiplier).to_i
else
pile_size += 1
end
end
end