Egg Drop Problems: They Are All They Are Cracked Up To Be!
Authors
Xiangwen Cao
Zongyun Chen
Steven J. Miller
Abstract
We illustrate how to invite and excite students about research by exploring higher-dimensional generalizations of the classical egg drop problem, in which the goal is to locate a critical breaking point using the fewest number of trials. Beginning with the one-dimensional case, we prove that with $k$ eggs and $N$ floors, the minimal number of drops in the worst case satisfies $P_1(k) \leq \lceil k N^{1/k} \rceil$. We then extend the recursive algorithm to two and three dimensions, proving similar formulas: $P_2(k) \leq \lceil (k-1)(M+N)^{1/(k-1)} \rceil $ in 2D and $P_3(k) \leq \lceil (k-2)(L+M+N)^{1/(k-2)} \rceil$ in 3D, and conjecture a general formula for the $d$-dimensional case. Beyond the critical point problems, we then study the critical line problems, where the breaking condition occurs along $x+y=V$ (with slope $-1$) or, more generally, $αx+βy=V$ (with the slope of the line unknown). We discuss how one frequently has to pivot from the original problem, which is intractable, to something that can be solved; in our case, using induction and recursion, two standard proof techniques.
