Egg Drop Problem
You have $K$ eggs and a building with $N$ floors. An egg breaks if dropped from floor $f^{*}$ or above, and survives intact (and can be reused) if dropped from any floor below $f^{*}$. You do not know $f^{*}$ in advance. Your goal is to find $f^{*}$ using the minimum number of drops in the worst case.
Work through the following scenarios:
- One egg, $N$ floors. What is the minimum worst-case number of drops, and why?
- Two eggs, $N$ floors. What is the optimal strategy, and how many drops does it require for $N = 100$?
- Infinite eggs, $N$ floors. What is the optimal strategy and worst-case drop count?
- General case: $K$ eggs, $N$ floors. Derive a recurrence relation and explain how to find the minimum number of drops.
Hints
- Think about the two extreme cases first -- one egg forces you into a linear scan, and unlimited eggs allow binary search. The two-egg problem sits between these: how do you exploit the second egg optimally?
- For two eggs, the key insight is to use decreasing step sizes. After the first egg uses one drop (and survives), the second egg has one fewer attempt available, so the next jump should be one floor shorter. This keeps the worst-case total constant.
- For the general $K$-egg case, flip the problem: instead of asking "how many drops for $N$ floors?", ask "how many floors can I guarantee to cover with $K$ eggs and $T$ drops?" This gives a clean recurrence: $f(K, T) = f(K-1, T-1) + 1 + f(K, T-1)$.
Worked Solution
How to Think About It: Think of this as a search problem under constraints. The constraint is that broken eggs cannot be reused -- so a reckless strategy that wastes eggs forces you to fall back on the slow, linear scan. The key tension is: dropping from a high floor gives you more information if the egg survives, but costs you more floor coverage if it breaks. With more eggs you can be aggressive (binary search); with fewer you have to be conservative. Before doing any math, get the two extremes straight in your head: one egg forces a linear scan, infinite eggs allow binary search. The interesting work is everything in between.
Quick Estimate: For $N = 100$ and $K = 2$, you need roughly $\sqrt{2N} \approx \sqrt{200} \approx 14$ drops. That is the right order of magnitude before you work out the exact formula. For general $K$, the minimum drops grows like $N^{1/K}$ -- each additional egg lets you take a $K$-th root of the problem size.
Approach: Work through each case systematically, then unify with a DP recurrence.
Formal Solution:
Case 1: One egg, $N$ floors.
With one egg you cannot risk anything. If you drop from floor 10 and it breaks, you have no egg left to probe floors 1-9 -- you lose all information about those floors. So you must test floors 1, 2, 3, ... in order. In the worst case (the critical floor is $N$), this takes $N$ drops.
$T_{\min}(1, N) = N$
Case 2: Two eggs, $N$ floors.
Now you have one egg to "probe" and one to "confirm." The strategy is to jump in decreasing step sizes. Drop the first egg at floor $k$, then $k + (k-1)$, then $k + (k-1) + (k-2)$, and so on.
Why decreasing steps? After each safe drop, you have used one attempt, so the second egg has one fewer floor to scan below the next jump. Making the steps shrink by 1 each time keeps the worst-case total constant regardless of where the egg breaks.
The total floors reachable in $T$ drops is: $k + (k-1) + (k-2) + \cdots + 1 = \frac{k(k+1)}{2}$
So choose the smallest $k$ such that $\frac{k(k+1)}{2} \geq N$.
For $N = 100$: we need $\frac{k(k+1)}{2} \geq 100$. Try $k = 13$:
$T_{\min}(2, 100) = 14 \text{ drops}$
Case 3: Infinite eggs, $N$ floors.
With unlimited eggs you can binary search: always drop from the middle floor. Each drop halves the search space regardless of outcome (break or survive). This gives:
$T_{\min}(\infty, N) = \lceil \log_2 N \rceil$
For $N = 100$: $\lceil \log_2 100 \rceil = 7$ drops.
Case 4: General case -- $K$ eggs, $N$ floors.
The direct DP over $(K, N)$ is awkward because $N$ can be large. A cleaner formulation: let $f(K, T)$ be the maximum number of floors you can check with $K$ eggs and $T$ drops.
At each drop from some floor $j$: - Egg breaks: you have $K-1$ eggs and $T-1$ drops left, and you know $f^{*}$ is below $j$. You can handle $f(K-1, T-1)$ floors below. - Egg survives: you have $K$ eggs and $T-1$ drops left, and you know $f^{*}$ is at or above $j$. You can handle $f(K, T-1)$ floors above.
So the total floors coverable from floor $j$ is $f(K-1, T-1) + 1 + f(K, T-1)$, and the optimal $j$ is chosen to make this as large as possible (which turns out to be any floor -- the expression does not depend on $j$ itself).
This gives the recurrence:
$f(K, T) = f(K-1, T-1) + 1 + f(K, T-1)$
Base cases: $f(1, T) = T$ (one egg, linear scan), $f(K, 0) = 0$ (no drops left, no floors covered), $f(K, 1) = 1$ (one drop, one floor tested).
The answer to the original problem is the minimum $T$ such that $f(K, T) \geq N$.
To compute this efficiently, iterate $T = 1, 2, 3, \ldots$ and fill the table row by row. Since $f(K, T)$ is non-decreasing in $T$, you stop as soon as $f(K, T) \geq N$. Time and space complexity is $O(K \cdot T_{\min})$.
Answer:
| Scenario | Worst-case drops | |---|---| | $K = 1$, $N$ floors | $N$ | | $K = 2$, $N = 100$ | 14 | | $K = \infty$, $N$ floors | $\lceil \log_2 N \rceil$ | | $K$ eggs, $N$ floors (general) | min $T$ s.t. $f(K,T) \geq N$, where $f(K,T) = f(K-1,T-1) + 1 + f(K,T-1)$ |
Intuition
The egg drop problem is really about information and insurance. Every drop gives you one bit of binary information -- break or survive -- but the cost of a "break" outcome varies wildly depending on how many eggs you have left. When you are egg-rich, a break is cheap (you just lost one tool). When you are down to one egg, a break is catastrophic (you lose all ability to probe). The optimal strategy dynamically adjusts how aggressively you search based on your remaining resource (eggs).
This shows up in a lot of real quant and systems work. In hypothesis testing, the number of "probes" you can afford before your budget (eggs) runs out determines how you allocate tests across parameter space. In sequential sampling, you face the same tension between aggressive early stopping and conservative confirmation. The DP formulation -- "how many floors can I guarantee to cover?" rather than "how many drops do I need?" -- is a useful trick whenever the state space of the direct formulation is large or hard to bound. Inverting the question often yields a cleaner recurrence.