The Egg Drop: Part 1

Introduction

This post is about a famous algorithmic optimization problem. My goal with this post is to try to apply calculus to discrete mathematics in a useful way. For some calculus is almost totally ignored in algorithmic analysis, even though (I think) it can be quite useful! This problem will show how.

Assume you are given n eggs to experiment with, and a building with h floors. You're in a magical world without terminal velocity, so when you drop an egg from a window on a given floor, the higher the floor that you drop the egg from, the harder it will hit the ground. You are tasked with figuring out which floor of the building is the highest floor that an egg can be dropped from without breaking upon impact.

You need to come up with a strategy that will provide the answer to this question by the time you have used up all n eggs. An egg is used up once it is broken by dropping it from a floor that is too high. The challenge is to describe an algorithm that will produce the answer as quickly as possible. That is, in the worst case scenario, you should have to conduct as few trials as possible, where a single trial consists of dropping an egg out of a certain window and observing whether or not it breaks. We will approach this problem by beginning with 1 egg, and then gradually increasing the number of eggs provided and noticing what pattern develops.

When n = 1, the problem is trivial. Since you only have one egg and you can't risk breaking the egg without figuring out the exact floor, you need to start at the bottom of the building and work your way up, dropping the egg from every floor until it breaks. Once the egg breaks, you know that the floor below that is the highest safe floor. In the worst case, this will take h drops.

With n = 2, the problem is significantly more challenging. You could take the same approach as in the n = 1 case, but then you would have wasted the advantage of having 2 eggs. How can we be as efficiently as possible?

Suppose you start by dropping from halfway up the building. For example, if h = 100 (the building has 100 floors), then you would start by dropping an egg from the 50th floor. If this egg doesn't break, then you've saved yourself the trouble of even testing the bottom half of the building, because if the egg doesn't break from the 50th floor, it won't break from any of the lower floors! If the egg does break, you have 1 egg left and 50 floors, so you work your way up from the bottom. The farthest you could possibly have to go is floor 49, so the worst case scenario is 50 drops, or h/2. This is much better than the worst case of h drops with n = 1. Note that we can only take this shortcut because we have 2 eggs. If we only had 1 egg, and we dropped it from floor 50 and it broke, then we would have used up our eggs without solving the problem. That would be unacceptable.

So, we can do slightly better with 2 eggs, but is dropping from halfway up the building the best we can do? What if we drop the first egg from 1/3 of the way up? In a 100 story building, this would be about floor 33. If the egg breaks, the worst case is 33 drops, since we have 1 egg remaining to test the bottom 32 floors. If the egg doesn't break, we can drop from floor 66, and then floor 100. If the first egg breaks at floor 100, then we only have to test floors 67-99 with the second egg. The total number of drops in the worst case here is the 3 drops with the first egg plus 32 drops with the second egg, which is 35, even less than the 51 drops with the halfway strategy!

It seems from these examples like the smaller the interval at which we drop our first egg, the more efficient we are. But that can't be true in general, because if we just drop the first egg at every floor, we're back to 100 drops total, which is really bad! How can we figure out the optimal division of labor between the two eggs?

In the next post, we will see how we can use calculus to quickly determine the solution.