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, 100 (the last step is capped at the top floor).Answer: Minimum worst-case drops = 14 using decreasing intervals.
Checked by running a model of the rule in a Python model. A computational check: a worst-case DP over all drop floors gives 14 drops for 2 eggs, the listed 14, 27, 39, ... plan really costs 14 at worst, steps of 10 cost 19, and 3 eggs need 9 drops (8 drops cover 92 floors, 9 cover 129).
Fixed steps of 10 give a worst case of 19 drops (10 on the first egg, then 9 linear on the second); each step must be one shorter than the last so every path costs the same.
How does the method generalize to 3 eggs and 100 floors? Model answer: with d drops and e eggs you can cover f(d,e) = C(d,1)+C(d,2)+...+C(d,e) floors. For e=3: d=8 covers 8+28+56 = 92 < 100, d=9 covers 9+36+84 = 129 >= 100, so 9 drops.
Say the first egg is dropped at floor x, then the steps shrink by one each time, so x, then x plus x minus one, and so on. That way every path costs the same, because each extra drop of the first egg leaves one fewer floor for the second egg to walk. I need x plus x minus one down to one to reach at least 100, so x times x plus one over two must be at least 100. That gives x equal to 14, since 14 times 15 over 2 is 105, so the answer is 14 drops in the worst case. The trap is fixed steps of ten, which cost 19 in the worst case.