Articles

The egg problem

The egg problem is a classic programming challenge. However, a mathematical solution exists. It is possible to solve this problem analytically, even in the general case with an arbitrary number of 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 survive the fall. If the egg survives, then it would have survived any lesser fall. If the egg breaks, then any greater fall would have broken it as well. The eggs are all identical and interchangeable. You’d like to find the minimum height that will break an egg. What is the fewest number of drops in which you are guaranteed to find the right 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 only egg, we’re forced to start at the ground floor. If the egg breaks, then we’ve found the right floor. Otherwise, we get to keep our egg, and we can try again with the next floor. Continuing on like this, the distance we can explore with 1 egg and t tries is:
d_1(t) = t.

Now let’s use this to solve the two-egg problem, where we start with 2 eggs and t tries: After we have dropped our first egg, we’ll have explored a single floor. If the egg broke, then we’ll have to explore the lower floors with 1 egg and t-1 tries. If the egg survived, then we’re free to explore the upper floors with 2 eggs and t-1 tries. Consequently, the overall distance we can explore with 2 eggs and t tries is:
d_2(t) = 1 + d_1(t-1) + d_2(t-1)
d_2(t) = 1 + (t-1) + d_2(t-1)
d_2(t) = t + d_2(t-1)

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

When we’re down to our last try, we can only use one egg. So d_2(1) = d_1(1) = 1. In general, extra eggs aren’t useful when we don’t have enough turns left to use them.

This gives us the closed-form solution:
d_2(t) = t + (t-1) + ... + 1
d_2(t) = t (t + 1) / 2

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

So, given two eggs, we’re guaranteed to find the right floor within fourteen tries.

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 surives, we’ll explore the upper d_n(t-1) floors. Consequently, the total distance we can explore is:
d_n(t) = 1 + d_(n-1)(t-1) + d_n(t-1) where t >= 2

From above, we have the solutions to the one- and two-egg problems:
d_1(t) = t for t >= 1

d_2(t) = t (t + 1) / 2 for t >= 1

Finally, extra eggs aren’t useful when there aren’t enough turns to use them:
d_n(t) = d_t(t) when t < n

Together, these statements give us the solution to every n-egg problem. For example, 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 general recurrence relation becomes:
d_3(t) = 1 + d_2(t-1) + d_3(t-1)
d_3(t) = 1 + (t^2 - t)/2 + d_3(t-1)

Expanding the recurrence relation gives:
d_3(t) = sum(1, i = 3..t) + sum((i^2)/2, i = 3..t) - sum(i/2, i = 3..t) + d_2(2)
d_3(t) = t(t^2 + 5)/6

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

So, given three eggs, we’re guaranteed to find the right floor within nine tries.