Answer to old chestnut: dropping glasses
First, consider the problem where you have only one glass.
In this case, the only sure way to determine N is to drop it from floor 1,
then drop it from floor 2, then from floor 3, etc. When it breaks, you
know N is that floor you just dropped the glass from.
After we break the first glass, we will be in this situation of having only
one glass, so we will have to proceed in a manner similar to this -- starting
on the lowest floor that could possibly be N and working up one floor at
So, with two glasses, let's begin by dropping a glass from some floor we'll
If it breaks, we now play the little game above on floors 1 through (possibly)
X-1. Either the glass will break somewhere in here, telling us N is that floor number, or it won't break, telling us N=X. The maximum is if N is X or X-1;
these cases require X drops.
If it doesn't break on floor X, then make a next drop be from some floor Y.
If this drop breaks, we can have up to X-2 additional drops of the other
glass to stay within a limit of X total drops (in the interest of
minimizing the number of drops in the worst case). So Y = X+(X-1).
If the glass does not break here, we keep on jump up by one floor less each
time, to floor X+(X-1)+(X-2), floor X+(X-1)+(X-2)+(X-3), etc.
In order to ensure we find N within X drops, the sum of
X+(X-1)+(X-2)+...+2+1 must be at least 100. If it's 100, exactly, then
in the case of N = 100 or 101 we'll get it when we drop a glass from the
100th floor and it either breaks or doesn't break.
This sum is equal to (X+1)*X/2, and the minimum X which works is 14.
So we can do it in 14 drops, by dropping the first glass from floor 14,
27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100 until it breaks, then
dropping the second glass on each floor between the last two drops,
starting from the bottom, and when it breaks, that's N, or if it doesn't
break, the floor where the first glass broke is N.