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 L₁, it may survive, and it may not. If it survives, we then drop it from a higher level L₂ > L₁; if it doesn't, we have to ensure that our remaining N-1 trials are enough to deal with the first L₁-1 levels, with egg #2 only. This means that L₁ can be no more than N.

By the same reasoning, if egg #1 survives the fall from level L₁, then we pick some new level L₂ from which to drop it. We then have N-2 trials left; and if egg #1 breaks, we need to have L₂-L₁ to be ≤ N-1. This pattern is repeated, with the inequality L_i+1-L_i ≤ N-i always holding. If L_K is the highest level from which egg #1 survives dropping, then necessarily K ≤ N. Also L_K=L₁+(L₂-L₁)+...+(L_K- L_K-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 L_K = 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 L₁=14, L₂= 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 L₁. 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 L₁=(N-1)N/2+1; similarly we may set L₂- L₁ = (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=1^N-1[(N-i)(N-i+1)/2+1] ≥ 100. The summation has a closed form, which is (N-1)(N²+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)(N²+N+6). Also, by what we argued above, we have a recurrence formula, namely H(N,k)=∑_i=1^N-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(M^1/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 M^1/k. (I.e., lim_{M → ∞} (log M)/M^1/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(M^1/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 log₂M eggs).