The Egg Drop: Part 3

Induction

In the previous post, we used calculus to determine an optimal strategy for solving the egg drop problem with 2 eggs. Now, what if n = 3 (that is, we have had 3 eggs instead of 2)? In this case, we can split the building into a certain number of sections with the first egg, then split the section of interest into subsections with the second egg, and then explore the final subsection with the last remaining egg.

So, what is the optimal number of sections and subsections that we should split the building into? Note that this problem contains the problem for n = 2 within it! That is, once we have broken the first egg while splitting the building into a number of sections, we have determined a certain section to search with 2 remaining eggs. This problem is then identical to the one we solved above. This allows us to assume two useful properties. First, we know the number of subsections that we want within each section will be the equal to square root of the size of the section:

Secondly, we know that the size of the subsections will be the same as the number of subsections within one section. We know this because the number of subsections in one section times the size of each subsection equals the size of one section, and the number of subsections per section is the square root of the section size, so the subsection size must also be equal to the square root of the section size (if a*b = c, and a*a = c, then a = b)!

In the worst case, then, the number of trials performed with the second egg will be equal to the number of drops performed with the third egg. (Actually, in determining the section if interest, we also test one of the floors in that section, so the third egg will have 1 less trial, just as the second egg in the n = 2 case had 9 drops vs. the 10 drops with the first egg. This discrepancy is not asymptotically significant, so we ignore it). Using these assumptions, we can create an expression for T, the total number of worst-case trials performed:

By setting the derivative equal to 0, we can solve for the optimal s₀ (number of sections created with the first egg):

Are you noticing a pattern here? When we have n eggs, the best strategy is to split the area of interest into x sections at every step, where x*x = n. The worst case number of trials will be the same for each egg, because we want to use each egg to its full potential in order to minimize the total number of trials. This can be proven rigorously using induction. The steps are almost identical to the derivation for 3 eggs above. We assume in the induction hypothesis that the last n-1 eggs all have an equal number of trials in the worst case, and that this number is equal to the rth root of h/s₀, where r = n -1. Then, the induction step, which is again almost identical to the derivation above, demonstrates that s₀ must be equal to the nth root of h. It follows very straightforwardly from this that all the other eggs also have an equal number of worst case trials.

Is this analysis even worth doing, even from a theoretical standpoint? It is easy to show that with n eggs, the worst case number of trials is equal to:

The actual number of worst case trials may be bounded by this plus some small constant (1?), but this is irrelevant for asymptotic analysis. The important point is that for some fixed number n of eggs, the worst case run time is bounded (big Theta) by the nth root of h, where h is the number of floors. Since different roots have different asymptotic growth, each additional egg actually provides an asymptotically significant advantage, making the run-time grow more slowly with the size of the input (number of floors of the building) from an asymptotic point of view.

There is, however, a limit to the benefits of using additional eggs. Once the number of eggs, n, reaches the log base 2 of the number of floors lg(h), we are splitting the building into 2 sections at every step. There is no algorithm more efficient than this, and adding additional eggs provides no additional benefit once n is greater than or equal to lg(h). We cannot split the building into fewer than 2 sections; treating it as 1 section would take us back to the naive strategy that is optimal for 1 egg, which is never efficient with more eggs.

That's it for this post! I hope you enjoyed the weird mix of calculus and induction.