The egg problem

The egg problem is a classic programming challenge. However, there is a mathematical solution. You can solve this problem analytically, even in the general case with \(n\) eggs.

The two-egg problem

Problem

You have a 100-story building and two eggs. When you drop an egg from any floor of the building, the egg will either break, or it will survive the fall: If the egg breaks, then any greater fall would have broken it as well. If the egg survives, then it would have survived any lesser fall. Every egg is identical and totally interchangeable. You’d like to find the lowest floor that will break an egg. What is the minimum number of tries in which you are guaranteed to find the lowest egg-breaking floor?

Solution

An egg could break at any time. When it does, we’ll be down to the one-egg problem. So we need to solve the one-egg problem first: How many floors can we explore with a single egg?

Since we can’t afford to lose our one and only egg, we’re forced to start at the ground floor. If the egg breaks there, then we’ve found the right floor. Otherwise, we get to keep our egg, and we can try again with the next higher floor. Continuing on like this, the distance we can fully explore with \(1\) egg and \(t\) tries is:
\(d_1(t) = t\) for \(t \geq 0\)

Now let’s use this to solve the two-egg problem, where we start with \(2\) eggs and \(t\) tries. When we drop an egg off a floor, we explore that floor. If the egg breaks, then we’re forced to explore the lower floors with \(1\) egg and \(t-1\) tries. But if the egg survives, then we can move on to the upper floors with \(2\) eggs and \(t-1\) tries. So the total distance that we can explore with \(2\) eggs and \(t\) tries is:
\(d_2(t) = 1 + d_1(t-1) + d_2(t-1)\)

Using the earlier solution to the one-egg problem:
\(d_2(t) = 1 + (t-1) + d_2(t-1)\)
\(d_2(t) = t + d_2(t-1)\)

We can expand this recurrence relation:
\(d_2(t) = t + (t-1) + ... + 1 + d_2(0)\)

When we’re out of tries, we can’t explore any further, no matter how many eggs we have left:
\(d_n(0) = 0\)

This gives the closed-form solution:
\(d_2(t) = t + (t-1) + ... + 1\)
\(d_2(t) = \frac{t(t + 1)}{2}\) for \(t \geq 0\)

In particular:
\(d_2(13) = 91\)
\(d_2(14) = 105\)

So, given two eggs, we’re guaranteed to find the right floor of a 100-story building within fourteen tries.

Strategy

We can use the recurrence relation from the previous section to get the sequence of floors from which we should drop our eggs:
\(d_2(t) = 1 + d_1(t-1) + d_2(t-1)\)

On the first attempt, we have \(2\) eggs and \(14\) tries:
\(d_2(14) = 1 + d_1(13) + d_2(13)\)

So our first attempt should be made on floor \(1 + d_1(13) = 14\).

If the egg breaks on the fourteenth floor, then we’ll switch to the \(1\)-egg algorithm and work our way up from the first floor. If the egg survives, then we’ll move on up to the \(d_2(13) = 1 + d_1(12) + d_2(12)\) branch of the recurrence relation. So our next attempt will be \(1 + d_1(12) = 13\) floors higher, on floor \(27\).

In the best-case scenario, the egg will break on the first floor, and we’ll be done in two tries. In the worst-case scenario, the egg will break on the thirteenth floor, and it will take all of our fourteen tries to find that out.

The \(n\)-egg problem

Problem

Given \(n\) eggs and \(t\) tries, how many floors can we explore?

Solution

Let’s start by dropping one egg: If it breaks, we’ll explore the lower \(d_{n-1}(t-1)\) floors; if it survives, we’ll explore the upper \(d_n(t-1)\) floors. Overall, the total distance we can explore is:
\(d_n(t) = 1 + d_{n-1}(t-1) + d_n(t-1)\)
\(d_n(0) = 0\)

We’ve already solved the one- and two-egg problems:
\(d_1(t) = t\) for \(t \geq 0\)
\(d_2(t) = \frac{t(t + 1)}{2}\) for \(t \geq 0\)

And, taken together, these statements give us the solution to every \(n\)-egg problem. In particular, here is the solution to the three-egg problem:

The three-egg problem

Problem

Given \(3\) eggs and \(t\) tries, how many floors can we explore?

Solution

When \(n = 3\), the \(n\)-egg recurrence relation becomes:
\(d_3(t) = 1 + d_2(t-1) + d_3(t-1)\)

Using the solution to the two-egg problem:
\(d_3(t) = 1 + \frac{(t - 1)t}{2} + d_3(t-1)\)
\(d_3(t) = \sum_{i=1}^t \frac{1}{2} ( i^2 - i + 2) + d_3(0)\)
\(d_3(t) = \frac{1}{2} \left( \frac{t(t + 1)(2t + 1)}{6} - \frac{t(t + 1)}{2} + 2t \right)\)
\(d_3(t) = \frac{t(t^2 + 5)}{6}\) for \(t \geq 0\)

In particular:
\(d_3(8) = 92\)
\(d_3(9) = 129\)

So, given three eggs, we’re guaranteed to find the right floor of a 100-story building within nine tries.