Two Eggs Generalized

Everyone knows the classic puzzle about dropping 2 eggs from a 100-story building:

You are given two eggs, and access to a 100-story building. Both eggs are identical. The aim is to find out the highest floor from which an egg will not break when dropped out of a window from that floor. If an egg is dropped and does not break, it is undamaged and can be dropped again. However, once an egg is broken, that’s it for that egg.

If an egg breaks when dropped from a certain floor, then it would also have broken from any floor above that. If an egg survives a fall, then it will survive any fall shorter than that.

The question is: What strategy should you adopt to minimize the number of egg drops it takes for the worst case to find the solution? (And what is the worst case for the number of drops it will take?)

Our goal in this article is to generalize the problem to arbitrarily many eggs and floors and try to solve it, but let’s first look at some edge cases. Obviously, if we have only one egg, then the only solution is to drop it from the first floor, then the second, then the third, and so on until it breaks. The worst case for this algorithm would be if the egg doesn’t break at all (which is a possibility) and consequently we would have to drop it $N$ times, if we are working with an $N$-story building. On the other end of the spectrum is the case of having a very large number of eggs (let’s say at least as much as the number of floors, for now). In this case the well known binary search algorithm solves the problem in $\lceil \log N\rceil$ drops, so having at least $\lceil \log N\rceil$ eggs ensures that we can run this algorithm.

Back to the case of two eggs. Before discussing the optimal solution let’s look at a family of solutions, in which we drop the first egg from $k$-th floor, then $2k$-th, then $3k$-th, and so on until it breaks at some point, let’s say by dropping from $mk$-th floor, which means that the highest safe floor is between $(m-1)k$ and $mk-1$, and can be found by checking those $k-1$ floors one by one with the second egg. We would achieve the maximum number of drops in this strategy if we dropped the first egg $q=\lfloor N/k\rfloor$ times (meaning that it would break in its last drop), and dropping the second egg another $k-1$ times, concluding that the worst-case complexity is $\lfloor N/k\rfloor + k - 1$. If $N=100$, then this strategy cannot do better than 19 drops, which is achieved by taking $k$ between 8 and 13 (see the picture below).

One might think this is good enough, but that’s where one would be mistaken. To see why this approach isn’t even close to optimal it helps to visualize the algorithm as a search tree, which will be discussed in detail in an upcoming article. In the case of this problem, the root of the tree represents the first chosen floor that we are dropping from, its left child corresponds to the next floor chosen to drop the second egg in case the first one broke, and its right child corresponds to the next floor chosen to drop the first egg in case it survives the first fall, and so on. The leaves of the tree represent the outcomes, but sometimes it’s more convenient to omit the leaves in the drawing, which we will adopt in this article, so each node represents a drop. For $N=21$ our current approach works best when $k=5$, whose tree is shown below.

Merely looking at this tree is enough to spot the problem: it’s not balanced enough, and perhaps performing the first drop from a higher floor and gradually decreasing the jump size could help us lure some of the nodes of the middle to the left and right sides. And indeed it does, as shown by the picture below.

What does this give us, one might wonder? Well, the number of drops for the worst case was $8$ with our previous method, and $6$ with the new one for the case of $21$ floors. One might argue that the difference isn’t much, but one would be mistaken, as for the case of $100$ floors the difference is $19$ vs $14$. The strategy for that case is to drop the first egg from 14th floor, then $14+13$th, then $14+13+12$th, and so on. How do we find these numbers is the next natural question to ask and look for an answer to. The answer is right in front of our eyes, as it turns out. Notice how the tree above looked a bit like a triangle, and for better or worse, $21$ happens to be a triangular number. It should be clear by now, that if the number of floors is a triangular number, then increasing it by even one more floor forces us to need another drop in the worst case (roughly speaking, the extra node has nowhere to fit in the tree without increasing its height). On the other hand, if we were to decrease the number of floors, we would have to go all the way down to the next smaller triangular number for the algorithm to halt a step sooner. This observation helps us determine the number of steps required for the optimal algorithm in the $N=100$ case. $100$ is between the consecutive triangular numbers $91$ and $105$, and using the fact that

\[105 = \binom{15}{2} = 1 + 2 + \cdots + 14\]

we conclude that we need $14$ steps. As for which floor should we drop from first, $14$ is a safe choice, as in the case of breaking the first egg, we can use the second egg to check the floors $1$ through $13$ in $13$ more steps, and the left side of the root would be “filled”. The next drop can be made from the floor numbered $14+13=27$, so that in the case of breaking the first egg, we can make $12$ more drops with the second egg to check the floors $15$ through $26$, and so on. The maximum number of floors $F(k)$ for which the problem can be solved, given that we are allowed to perform at most $k$ drops is therefore given by the formula

\[F(k) = 1 + 2 + \cdots + k = \binom{k+1}{2}.\]

Given the number of floors we can also find a formula for the required number of steps for the optimal algorithm (a good exercise), which is

\[d = \left\lceil \frac{\sqrt{1 + 8N} - 1}{2} \right\rceil.\]

Now that we’ve gotten the dry parts out of the way, it’s time for the juicy part — variable number of eggs. As you may have already guessed, we’re going to work with a certain kind of generalization of triangular numbers, namely, tetrahedral numbers for three eggs, pentatope numbers for four eggs, and the so-called $n$-simplex numbers for $n$ eggs.

Let $F(n,d)$ denote the maximum number of floors we can handle with $n$ eggs and at most $d$ drops. We’ve already seen that $F(2,6)=21$, for instance. The key observation here is that if we have $n$ eggs and $d$ drops left, and we drop an egg from floor $x$ it will cost us one drop (so $d$ becomes $d-1$), and the egg will either break or not. In case it breaks, we are left with $n-1$ eggs and $d-1$ drops to check the floors below $x$, of which there are at most $F(n-1,d-1)$. In case it doesn’t break we are left with $n$ eggs and $d-1$ drops to check the floors above $x$, of which there are at most $F(n,d-1)$. Together with the $x$-th floor these make up the whole $N = F(n,d)$-story building (see the picture below).

We get the recurrence relation

\[F(n,d) = F(n,d-1) + F(n-1,d-1) + 1,\]

with initial conditions

\[F(0,d)=0 \quad \text{(no eggs, nothing to test)},\] \[F(n,0)=0 \quad \text{(no drops, nothing to test)}.\]

To be continued