The Egg-Drop Problem

You have two identical eggs and a 100-floor building. There's a floor $F$ (unknown to you, somewhere from 0 to 100) such that an egg dropped from floor $F$ or below survives, and from above $F$ it breaks. You want to find $F$ exactly. If an egg breaks, you can't reuse it; you have only two eggs total. What's the fewest drops that guarantees you find $F$, no matter what $F$ turns out to be?

Give it a real attempt before reading on. The trap is trying to reuse the pure halving strategy from ordinary binary search, it feels natural, but it quietly assumes you can afford unlimited failed tests, and here a break costs you your only backup.

Why plain binary search fails

With unlimited eggs, you'd binary search: drop from floor 50, then 25 or 75, and so on, needing about $\log_2 100 \approx 7$ drops. But with only two eggs, binary search is dangerous: drop from floor 50 and it breaks, and you're down to one egg with 49 remaining floors to check, and a single egg forces you to test floor by floor, linearly, from the bottom, because you can no longer afford a break. In the worst case that's up to 49 more drops. Naive halving front-loads too much risk onto the first egg.

Balancing the two costs

The right approach uses egg 1 to test at decreasing intervals, so that no matter when it breaks, the work remaining for egg 2 (which must now search linearly) is roughly the same across all break points. Drop egg 1 from floor 14, then (if it survives) floor 27, then 39, then 50, then 60, then 69, then 77, then 84, then 90, then 95, then 99, then 100, each gap one smaller than the last (14, 13, 12, 11, …). If egg 1 breaks on a given drop, egg 2 sweeps up linearly, floor by floor, through the gap left below that drop.

Why decreasing gaps? Because every drop of egg 1 "costs" one drop already spent, and if it breaks on the $k$-th such drop, egg 2 needs at most (gap size $-1$) more drops to finish, so you want (drops spent so far) + (remaining linear sweep) to be roughly constant across every possible break point. Starting the gap at 14 and shrinking by 1 each time makes the total drops needed at most 14 in every scenario: $14 + 13 + 12 + \cdots + 1 = 105 \geq 100$, so 14 first-egg drops comfortably cover a 100-floor building, and no branch needs more than 14 drops total.

Worked example: $F = 60$

Drop 1: floor 14, survives (1 drop used, egg 1 still alive). Drop 2: floor 27, survives (2 drops). Drop 3: floor 39, survives (3). Drop 4: floor 50, survives (4). Drop 5: floor 60, survives (5), wait, $F=60$ means it should just survive at 60 and break above; survives means $F \geq 60$. Drop 6: floor 69, breaks (6 drops, egg 1 gone). Now egg 2 sweeps floors 61, 62, …: drop 7 at 61 (survives), drop 8 at 62 (survives)… up through drop 14 at 68 (survives), confirming $F = 68$ is wrong, actually since egg 1 broke at 69, $F$ is somewhere in 60–68, and egg 2 checks 61 through 68 one by one, needing at most 8 more drops (drops 7–14). Total: at most 14 drops, matching the bound regardless of exactly where $F$ falls.

The transferable technique

This is a worst-case cost-balancing problem: with limited "tries" of an expensive resource (an egg, a risky order, a costly experiment), the optimal strategy equalizes the worst-case total cost across every branch of the decision tree, which usually means front-loading bigger, riskier steps early and shrinking them over time. The same shape of reasoning generalizes directly to $k$ eggs and $n$ floors, and to any situation with a scarce number of "destructive tests" and a search space to narrow down.