A puzzle to pass the time

September 14, 2007

Here’s something to work on if you have nothing better to do, or if you do have something better to do, but want to do this anyway.

There is a staircase with 100 stairs. You are given two glass balls and the task of determining which is the highest step they can be dropped from without breaking. What is the optimum method for determining this step?

Additional rules and clarifications.
1. The only experiment you may do is dropping the balls from a step and seeing whether they break.
2. Optimum in this case is defined as performing the least number of tests in the worst case scenario.
3. No matter what step the ball is dropped from it falls all the way to the bottom of the staircase.
4. If the ball breaks at step N, it breaks at all higher steps.
5. Once a ball is broken, it cannot be used in further tests. So if you break both balls without determining the answer, you lose.

If this puzzle was too easy for you, you can try the case where there are N stairs, or M balls, or both. I haven’t done these general cases, so I don’t know how hard they might be.