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

By the same reasoning, if egg #1 survives the fall from level L_{1}, then we pick some
new level L_{2} from which to drop it. We then have N-2 trials left; and if
egg #1 breaks, we need to have L_{2}-L_{1} 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_{1}+(L_{2}-L_{1})+...+(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_{1}=14, L_{2}= 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_{1}. 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_{1}=(N-1)N/2+1; similarly we may set L_{2}-
L_{1} = (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^{2}+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^{2}+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_{2}M eggs).