Egg Drop Problems: They Are All They Are Cracked Up to Be!

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 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 P1(k)≤⌈kN1/k⌉. We then extend the recursive algorithm to two and three dimensions, proving similar formulas: P2(k)≤⌈(k−1)(M+N)1/(k−1)⌉ in 2D and P3(k)≤⌈(k−2)(L+M+N)1/(k−2)⌉ in 3D, and conjecture a general formula for the d-dimensional case. Beyond the breaking point problems, we then study the breaking 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.