crystal balls and the floor from which they break

There are two identical crystal balls and one needs to find out which is the maximum floor in a 100 storey building from where the balls can fall before they break. In the most efficient way, what will be the maximum number of drops required to find the right floor in any possible scenario? The balls are allowed to be broken (if required) while finding the right floor.


Solution 1 (Constant interval, not optimal):

import sys

min_drops = 100
min_interval = 1
for interval in range(1,50):
    drops = 100/interval + max(100%interval, interval-1)
    print "interval " , interval , " drops " , drops
    if drops < min_drops:
        min_drops = drops
        min_interval = interval

print "min_interval ", min_interval, " min_drops ", min_drops

Solution 2 (increasing interval, not optimal):
seq = (1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 100)
count(seq) = 14.
worst case = 14 + 8 = 22


Solution 3 (decreasing interval, optimal, best solution):
14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 100

The advantage with decreasing interval is that, when the crystal ball breaks
the number of trails required to determine the floor at which it breaks gets
smaller everytime.,

One method to decrease the interval is to find a number n, such that
∑n >= no_of_floors,
and then start from interval n, n+n-1, n+n-2 , .... 100
so when the ball breaks at 100, the number of trails required is the difference
b/w previous floor and current floor.

we have ∑n = n(n+1)/2 >= 100
solving the above equation gives, n = 14
so we will test from:
#14, #(14 + 14 - 1 = 27), #(27 + 14 - 2 = 39), #(39 + 14 - 3 = 50), #(50 + 14 - 4 = 60), #(60 + 14 - 5 = 69), #(69 + 14 - 6 = 77), #(77 + 14 - 7 = 84), #(84 + 14 - 8 = 90), #(90 + 14 - 9 = 95), #(95 + 14 - 10 = 99), and finally from #100.