The Two Egg Problem

Question

A building has 100 floors. There is a critical floor F: eggs dropped from floor F or above break; below, they survive (and can be reused). You have exactly 2 eggs. What is the minimum number of drops that guarantees you identify F (which may be anywhere in 1..100, or "never breaks"), and what's the strategy?

Accepted Answer

14 drops. When the first egg breaks, the second egg must linearly scan the gap below it, so a fixed step size s for egg one costs up to frac100s + s - 1 drops; minimizing gives s = 10 → 19 drops. But fixed steps waste budget: late first-egg breaks have already spent many drops, yet still face a full gap scan. Equalize the worst case. If the answer is n drops total, the first egg's drops can come from floors with decreasing gaps n, n-1, n-2, dots: if it breaks on its j-th drop, you've used j drops and have n - j left, exactly enough to scan the gap of size n - j. Coverage with budget n: n + (n-1) + dots + 1 = fracn(n+1)2 ge 100 implies n = 14 ;; (tfrac14 cdot 152 = 105 ge 100). Strategy: drop egg 1 at floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100; on a break, scan from one above the previous safe floor. Worst case 14 drops everywhere. Takeaway: under a budget, optimal strategies equalize worst-case cost across branches, the same minimax logic as balancing risk across scenarios in a book. The general answer for e eggs is the largest n with sum_i=1^ebinomni ge textfloors.

The Two Egg Problem

Problem

Your answer

Hints

More Brainteasers & Logic to train on