The Egg Drop With k Eggs and n Floors

The familiar version of this puzzle gives you two eggs and a 100-floor building, and asks for the minimum number of drops that guarantees finding the highest floor an egg survives falling from, in the worst case. The general version replaces "two eggs" with $k$ eggs and asks the same question. Naively, more eggs should make the answer harder to compute, but the trick that cracks the two-egg case scales cleanly to any $k$.

The key reframe: instead of asking "with $k$ eggs and a budget of $d$ drops, how many floors can I test?", flip it around and ask "with $k$ eggs and $d$ drops, what is the maximum number of floors I can definitively resolve?" Define $f(d, k)$ as that maximum. A single drop either breaks the egg (leaving $k-1$ eggs and $d-1$ drops to search below) or doesn't (leaving $k$ eggs and $d-1$ drops to search above), plus the one floor just tested. That gives the recurrence

$$f(d, k) = f(d-1, k-1) + f(d-1, k) + 1$$

with $f(d, 1) = d$ (one egg forces a linear floor-by-floor search) and $f(0, k) = 0$. The answer to "minimum drops needed for $n$ floors and $k$ eggs" is the smallest $d$ with $f(d, k) \ge n$.

For $k = 2$ eggs and $n = 100$ floors: building up $f(d, 2)$ for $d = 1, 2, \dots$ gives $2, 5, 9, 14, \dots$ following $f(d,2) = f(d-1,1) + f(d-1,2) + 1$, and it first reaches 100 at $d = 14$ — the well-known answer to the original puzzle.