display | more...
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 a time.

So, with two glasses, let's begin by dropping a glass from some floor we'll call X.

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.

Log in or register to write something here or to contact authors.