The egg problem

The two-egg problem

Problem

You have a 100-story building and two eggs. You can drop an egg from the window of any floor. When the egg hits the ground, it will either break, or it won’t. If the egg breaks, then any greater fall would have broken it as well. If the egg survives, then would have survived any lesser fall. Assume that the eggs are identical (until they are broken) and will never fatigue.

What is the minimum number of tries in which you are guaranteed to find the lowest egg-breaking floor?

The lowest egg-breaking floor could be any floor, so you won’t know the right floor until you actually drop an egg there and watch it break.

Solution

When we drop an egg, it could break. If it breaks, we’ll be down to the one-egg problem: How many floors can we explore with one egg?

We will need the one-egg solution to solve the two-egg problem, where we have eggs and tries.

We know we’ll have to start by dropping one of our eggs from some floor—although we don’t yet know which floor that will be. If the egg breaks on that first drop, then we know the lowest egg-breaking floor is below us, and we will have only egg and tries with which to find it. From the one-egg problem, we know that we can explore at most floors with that one egg. So we should start on the floor. When our first egg breaks, we’ll move to the ground floor, and gradually work our way up through the lower floors until we find the lowest egg-breaking floor. This could take all of our remaining tries.

On the other hand, if the egg survives that first drop, then we’ll know that the lowest egg-breaking floor is above us, and we’ll have eggs and tries with which to find it. From the two-egg problem (which we haven’t yet solved), we know that we can explore upper floors.

So the total distance, below and above us, that we can explore with eggs and tries is:

When we’re out of tries, we can’t explore any further, no matter how many eggs we have, so:

This gives the solution:

for

In particular:

So we are guaranteed to find the lowest egg-breaking floor within fourteen tries.

The -egg problem

Problem

Given eggs and tries, how many floors can we explore?

Solution

Let’s start by dropping one egg: If it breaks, we’ll explore the lower floors; if it survives, we’ll explore the upper floors. Either way, one of these two formulas will give us the location where we should drop our next egg.

Taken together, the total distance we can explore is:

We’ll have to stop when we’re out of tries:

We’ve already solved the one- and two-egg problems:
for
for

So we can find:





for

From there, we can find , …, , and so on, up to any .

In particular, if we’re given a 100-story building and three eggs, then:

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