Two Eggs, 100 Floors: Puzzle and Step-by-Step Solution
Logic & Strategy
Medium
Reported at Citadel, Two Sigma, Hudson River Trading, Jane Street
The puzzle
You have two identical eggs and a 100-storey building. There is some floor at or above which an egg breaks when dropped, and below which it survives. A dropped egg that survives can be reused. What is the minimum number of drops that guarantees you find the highest safe floor?
Short answer: Fourteen. Drop the first egg from floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99 and 100, then search the gap one floor at a time with the second egg.
Step 1: What the second egg forces
Once the first egg breaks, you have one egg left, and you cannot risk breaking it before you know the answer. So you must test the floors in the gap one at a time from the bottom. If the first egg broke at floor f and last survived at floor g, that costs up to f - g - 1 more drops.
That makes the problem a balancing act: big jumps with the first egg save drops early but leave a long linear search afterwards.
Step 2: Why equal jumps are not optimal
Jumps of 10 (drop at 10, 20, ..., 100) cost up to 10 drops for the first egg plus 9 for the second, 19 in the worst case. The problem is that the worst case for the second egg is the same in every gap, while the first egg's count keeps climbing. Each extra first-egg drop should be paid for by a shorter gap.
So if you allow k drops in total, make the first jump k floors. If it breaks, you need at most k - 1 more drops. If it survives, you have used one drop, so the next jump should be k - 1 floors, then k - 2, and so on.
Step 3: Find the smallest k
With decreasing jumps you cover k + (k - 1) + ... + 1 = k(k + 1)/2 floors. You need that to be at least 100. For k = 13 it is 91, too few. For k = 14 it is 105, enough. So 14 drops suffice.
The first egg goes from floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95 and 99, then 100. Check the worst case at each step: breaking at 14 leaves floors 1 to 13 to test, 1 + 13 = 14 drops. Breaking at 27 leaves 15 to 26, 2 + 12 = 14 drops. The total stays at 14 throughout.
Step 4: Why 13 cannot work
With 13 drops, the first drop can be no higher than floor 13, because if it breaks there you need 12 more drops to test floors 1 to 12. After that, the second jump can be at most 12 floors, and so on. The most you can cover is 13 + 12 + ... + 1 = 91 floors, which is fewer than 100. So 14 is optimal.
In general, with e eggs and d drops you can cover the sum of C(d, i) for i from 1 to e floors, which reproduces d(d + 1)/2 for two eggs.
Why interviewers ask it
Interviewers want the insight that the jump size should shrink by one each time, then the triangular-number bound. Proving 13 is too few is what makes the answer complete.
Knowing the proof is half of it. Work Two Eggs, 100 Floors interactively, then take it under a clock with the rest of the Outcry simulators.