The Egg Drop: Part 2

Using Calculus

Previously, I introduced the egg drop problem. Now, we will apply calculus to help optimize our algorithm.

The trick here is to model the total number of drops as a mathematical function. Notice that the general approach described above is to use the first egg to "split" the building into a certain number of equally sized sections, and test these sections from the bottom up. Once you know which section the desired floor lies in, we can use the second egg to pinpoint the exact floor.

In the worst case scenario, where the desired floor is the second highest floor, the total number of trials we perform with the first egg is equal to the number of sections we are splitting the building into. For example, if we split the building into 2 sections, we would drop the first egg from the middle floor and it would remain unbroken; then, we would drop it from the top floor and it would break, so we would have to work our way up with the second egg.

So the first egg undergoes at most s drops, where s is the number of sections we are dividing the building into. The size of any given section of the building is then h/s. Notice that we may have to test the entire section once the first egg breaks; to be safe, we have to start the second egg from the bottom of the given section and work our way up. Therefore, the second egg undergoes at most h/s drops.

Hence, we can represent the total number of trials in the worst-case scenario as a function of the number of sections we choose to divide the building into according to our strategy:

We want to minimize T, the number of trials, by choosing an optimal number of sections to divide the building into by dropping the first egg at certain intervals. The easiest way to determine the optimal value for s to minimize T is to take the derivative of the expression above and set it equal to zero. As always, calculus is great for optimization.

A few caveats: in general, this approach could produce multiple solutions, which could be maxima as well as minima. Finally, optimization with calculus helps us to find local extrema, and the global minimum does not necessarily have to be a local minimum recognizable by differentiation (it could be one of the endpoints of the domain). Finally, this problem, like most algorithmic problems, is discrete by nature, whereas calculus relies on differentiability. If calculus instructs us to split the building into pi/2 sections, then we might be in trouble, because we have only integer numbers of floors to work with. Nevertheless, in this case, we will see that this approach is an extremely elegant way to determine the exact solution.

Differentiating the expression for total worst-case number of trails, we find:

When we set the derivative to zero, we find:

This indicates that the number of sections we should divide the building into is equal to the square root of the height of the building in floors. That is, for the 100 story building, we would start by dropping the first egg at floor 10, then floor 20, etc. Once the first egg broke, we would only have 9 floors remaining to test, so the worst case scenario is that the first egg breaks after 10 drops and then the second egg is dropped 9 times, for a total of 19 drops.

Actually, the optimal solution to this problem is slightly more complicated than the solution just described above. Suppose we drop the first egg at floor 10 and it doesn't break. Then, we have 2 eggs remaining and 90 floors. But, the math we just did shows that in such a scenario, the best strategy is to split the remaining floors into x sections, where x is the square root of the number of floors. The square root of 90 is approximately 9, so the best strategy would be to split the 90 remaining floors into 9 sections. We would begin by dropping at floor 20. Then, we would have 80 floors, which we would still want to split into approximately 9 sections. Therefore, we would next drop at floor 29, instead of floor 30! This is extremely confusing. For the purposes of this blog, we will not recalculate the optimal algorithm at every drop, even though from a purely theoretical standpoint that is more efficient (assuming that the actual climbing of stairs in the building and dropping of the egg is much more difficult and time-consuming than the calculation).

In this post, we saw how to use calculus to solve the case for n = 2. But, what if we have even more eggs? Is there some way to reuse our insights from the n = 2 case to derive a more general solution? In the next post, we will use induction to generalize our results. (I will not actually do rigorous induction, but I will give an example that will show the framework that could be used to prove the result by induction).