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.