### PUZZLE #8: CUSHIONING AN EGG (SOLUTION)

For the moment, suppose you have just one egg. The only way you can guarantee a determination of X is to first try level 1; then, if the egg survives, level 2, and so on. So the number of trials (drops)--without leaving anything to chance--is N=100.

Now let's go back to the original problem, where we have two eggs, egg #1 and egg #2. Let's assume that N is our guaranteed number of trials and that we never repeat a trial. If our first trial is to drop egg #1 from level L1, it may survive, and it may not. If it survives, we then drop it from a higher level L2 > L1; if it doesn't, we have to ensure that our remaining N-1 trials are enough to deal with the first L1-1 levels, with egg #2 only. This means that L1 can be no more than N.

By the same reasoning, if egg #1 survives the fall from level L1, then we pick some new level L2 from which to drop it. We then have N-2 trials left; and if egg #1 breaks, we need to have L2-L1 to be ≤ N-1. This pattern is repeated, with the inequality Li+1-Li ≤ N-i always holding. If LK is the highest level from which egg #1 survives dropping, then necessarily K ≤ N. Also LK=L1+(L2-L1)+...+(LK- LK-1) ≤ N + (N-1) + (N-2) +...+1=N(N+1)/2. Now if egg #1 never breaks--and this is a possibility--it must be the case that LK = 100. Thus N(N+1)/2 must be at least 100, and hence N must be at least 14. An algorithm that guarantees 14 trials is obtained by letting L1=14, L2= 14+13=27, etc. Since 14(14+1)/2=105, it's conceivable the first egg doesn't break until level 99=105-(3+2+1). This would then be the 11th trial. If the egg breaks, after having survived a drop from level 95=105-(4+3+2+1), you have three more trials to determine X, where 96 ≤ X ≤ 98. If the egg doesn't break, you can determine whether X=100 in one more trial.

So what we've sorted out above is that if you have two eggs, and are limiting yourself to N trials, then the tallest tower you can use to determine X is N(N+1)/2 feet high. So suppose we now have three eggs to work with. Suppose you start with dropping egg #1 from level L1. If it breaks, then you have N-1 trials left; so you therefore have a tower of (N-1)N/2 feet, for which you can guarantee a determination of X. Thus we may set L1=(N-1)N/2+1; similarly we may set L2- L1 = (N-2)(N-1)/2+1, etc. Thus, in order to find the optimal value for N such that X may be determined in ≤ N steps with three eggs, we need the smallest N such that ∑i=1N-1[(N-i)(N-i+1)/2+1] ≥ 100. The summation has a closed form, which is (N-1)(N2+N+6)/6, from which we obtain N=9. (So your first drop is from level (9-1)9/2+1=37.)

Let's adopt some notation, and let H(N,k) be the height of the tallest tower you can use to determine X if you have at most N trials and k eggs. As shown above, H(N,1)=N, H(N,2)=N(N+1)/2, and
H(N,3)=(N-1)(N2+N+6). Also, by what we argued above, we have a recurrence formula, namely H(N,k)=∑i=1N-1[H(N-i,k-1)+1], which you can easily show by induction to be a polynomial of degree k in unknown N. For the computer scientist, this suggests that if the original tower has height M feet, then the optimal algorithm for computing X with k eggs has O(M1/k) steps. But this now suggests a further problem: Suppose your tower is M feet and you have an unlimited number if eggs to test with. Shouldn't your optimal algorithm be a binary search, which has O(log M) steps? (The logarithm base is not important in this notation.) And everybody knows that log M grows more slowly than M1/k. (I.e., limM → ∞ (log M)/M1/k=0.)

The way out of this conundrum is to remember what is being held fixed and what is being allowed to vary. In the algorithm analysis O(M1/k), k is fixed and M is allowed to increase without bound; in the O(log M) analysis, k is effectively infinite (though in any given case of M, you can get away with using roughly log2M eggs).