The two-egg dropping puzzle
You have 2 identical eggs and a building with 100 floors. There is an unknown threshold floor such that an egg breaks when dropped from that floor or above and survives from any floor below, and an egg that survives can be reused. What is the smallest number of drops that guarantees finding the threshold in the worst case, and what strategy achieves it?
History and references
Solved by folklore.
The puzzle is a staple of programming interviews and a standard example of dynamic programming. If you are allowed drops, the first drop can be at most at floor , because if the egg breaks the remaining drops must test the floors below one at a time with the second egg. The next drop can be at most floors higher, and so on, so drops cover at most floors. Since , the answer is 14, for example dropping from floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99 and 100 until the first egg breaks. In general, drops with eggs can cover floors.
References
Solutions 0
Sign in or create an account to publish a solution