With two eggs and a building with 100 floors, what is the optimal strategy for finding the lowest floor at which an egg will break when dropped? Followup: What if the number of floors of the building is unknown?

Heard from a Googler in 2005.

(Thanks to Mike who posted this solution as a comment at Puzzles Page)

At any point, if you are left with only 1 egg, the only strategy that will give you the answer is to start at the lowest unknown floor and work your way up one-by-one until the egg breaks or until you reach the top floor.

With 2 eggs, you can improve your strategy by starting somewhere between the lowest unknown floor and the highest unknown floor. If the egg breaks, you can eliminate all upper floors, but then you have to revert to the 1 egg strategy. If the egg doesn't break, you can eliminate that floor plus all floors below it, and then choose another starting point among the remaining floors and repeat.

With 100 floors, you can find the correct floor in 14 drops or less by starting at floor 14. If the egg breaks, you then go to floor 1, work your way up, and will find the correct floor with at most 14 drops. If the egg doesn't break, then move up 13 floors to 27. Again, if it breaks, you work your way up from 15 and will find the correct floor in at most 14 drops. If it didn't, you move up 12 floors, then 11, etc. Using this method, you can see that you will always find the correct floor in 14 or fewer drops.

If you attempt to find the floor with 13 or fewer drops, you can see that you must start at the 13th floor or lower, and after the first drop you can move at most 12 floors, then 11, etc. You will not reach the top of the building within 13 drops, so you cannot guarantee you will find the correct floor.

Therefore, any strategy will in worst case require at least 14 drops.

For an extensive discussion of this problem, see the article The Egg Game by William Gasarch and Stuart Fletcher, Sep 2008.