Difficulty: Medium · Puzzle 2 of 6 · Topic: Classic Brain Teasers
You have 2 identical eggs and a 100-floor building. Find the highest safe floor in the worst case with minimum drops.
Use decreasing step sizes so worst-case paths equalize.
1) Suppose first egg drops at floors x, x+(x-1), x+(x-1)+(x-2), ...
2) If first egg breaks on k-th drop, second egg does linear search in previous interval of size at most x-(k-1)-1.
3) Worst-case drops are x because first-egg drop count plus second-egg linear steps is bounded by x.
4) Need x + (x-1) + ... + 1 >= 100 => x(x+1)/2 >= 100.
5) Smallest integer x is 14 since 14*15/2 = 105.
6) Strategy: drop at 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, ...Answer: Minimum worst-case drops = 14 using decreasing intervals.
Using fixed interval 10 gives up to 19 drops, not optimal worst case.
How does the method generalize to 3 eggs and 100 floors?