It is not a problem of bravery or patience, but of worst-case design. All its elegance lies in finding a plan that shines not when everything goes right, but when everything goes wrong.
The 100-story building and the two eggs
Riddle statement
You have two identical eggs and access to a 100-story building.
There is a critical floor such that:
- if an egg is dropped from that floor or from a higher one, it breaks;
- if it is dropped from a lower floor, it does not break.
You need to determine that critical floor while minimizing, in the worst case, the number of drops.
What is the smallest number of drops you can guarantee in the worst case, and what strategy achieves it?
Show solution
Solution
Answer: the minimum in the worst case is 14 drops.
You have to balance two risks:
- if the first egg breaks too soon, you need many linear tests with the second egg;
- if you save it for too long, you spend too many drops climbing upward.
The optimal strategy reduces the jump size by one after each test. Drop the first egg from:
- floor 14,
- floor 27,
- floor 39,
- floor 50,
- and so on, adding one less floor each time.
With this design, if the egg breaks on any test, the number of floors left to check with the second egg exactly matches the number of drops still available. Nothing is wasted.
We need the smallest integer \(n\) such that
Since \(14 \cdot 15 / 2 = 105\), the minimum value is \(n = 14\).
That is the guaranteed number of drops in the worst case.