xiii. Egg Dropping

Problem. With $e$ eggs and a building of $N$ floors, find the highest floor from which an egg survives, minimizing the worst-case number of drops. A broken egg is lost; a surviving egg can be reused.

Invert the question: with $e$ eggs and $d$ drops, how many floors $F(e,d)$ can be handled? Drop from floor $F(e-1,d-1)+1$: if it breaks, $F(e-1,d-1)$ floors below remain with one egg less; otherwise $F(e,d-1)$ floors above remain. So $F(e,d)=F(e-1,d-1)+1+F(e,d-1)$, whose solution is $F(e,d)={\sum }_{i=1}^e\left(\genfrac{}{}{0ex}{}{d}{i}\right)$.

Eggs	Answer
1	$N$ drops (linear scan from the bottom)
2	smallest $d$ with $d(d+1)/2\ge N$: 14 for 100 floors
$e\ge {\log }_2(N+1)$	binary search, $\lceil {\log }_2(N+1)\rceil$
general	binary search on $d$ with $F(e,d)$

long long eggFloors(int eggs, long long drops) {   // max floors decidable: sum_{i=1..eggs} C(drops, i), capped
    long long s = 0, c = 1;
    for (int i = 1; i <= eggs && i <= drops; i++) {
        c = c * (drops - i + 1) / i;               // exact: C(d, i) = C(d, i-1) * (d-i+1) / i
        s += c; if (s >= (long long)4e18 || c >= (long long)4e18) return (long long)4e18;
    }
    return s;
}
long long minDrops(int eggs, long long floors) {   // smallest d with eggFloors(eggs, d) >= floors
    long long lo = 0, hi = floors;
    while (lo < hi) { long long m = (lo + hi) / 2; if (eggFloors(eggs, m) >= floors) hi = m; else lo = m + 1; }
    return lo;
}

Proof: F(e, d) = sum of C(d, i)

The recurrence $F(e,d)=F(e-1,d-1)+F(e,d-1)+1$ with $F(0,d)=F(e,0)=0$ is optimal: the first drop splits the floors into “below” (handled with $e-1$ eggs and $d-1$ drops) and “above” (with $e$ eggs and $d-1$ drops), and no strategy can handle more. Let $G(e,d)={\sum }_{i=1}^e\left(\genfrac{}{}{0ex}{}{d}{i}\right)$. Then $G(e-1,d-1)+G(e,d-1)+1={\sum }_{i=1}^{e-1}\left(\genfrac{}{}{0ex}{}{d-1}{i}\right)+{\sum }_{i=1}^e\left(\genfrac{}{}{0ex}{}{d-1}{i}\right)+\left(\genfrac{}{}{0ex}{}{d-1}{0}\right)={\sum }_{i=1}^e\left(\left(\genfrac{}{}{0ex}{}{d-1}{i-1}\right)+\left(\genfrac{}{}{0ex}{}{d-1}{i}\right)\right)=G(e,d)$ by Pascal’s rule, with the same boundary values. $F$ is increasing in $d$, so the minimum $d$ is found by binary search. Tested against the classical $O(e{N}^2)$ DP for $e\le 4$, $N\le 120$.