I am in a 100-story building. I have with me two glass balls. I know that if I throw a ball out of the window, it won't ever break if the floor number is less than X, and it will always break if the floor number is equal to or greater than X. Assuming that I can reuse the balls which don't break, find X in the minimum number of throws.
Suppose we have a strategy with N throws. Then the floor is defined by two numbers: the throw in which the first ball breaks, and the throw in which the second ball breaks. The sum of these two numbers should be less than or equal to N. Hence, the number of floors we can distinguish is the number of different pairs of such numbers, which is equal to N(N+1)/2. This number should be more than 99. Hence, we need at least 14 throws.
Now we would like to build a strategy. To decide the floor for our first throw, we observe that if the ball breaks we need to decide between the leftover floors in 13 steps. Which means, to maximize our choices for the case when it doesn't break, we need to use all the opportunities. That is, we should throw the ball from the 14th floor first. If it breaks, we use the second ball starting from the first floor up.
The second throw should be from the 14 + 13 = 27th floor. And so on.
Last revised April 2006