You live in a 36-story apartment building, and have access to a window on each floor.

First, let me explain my point of view about what is being asked.

Suppose that the nth floor is the lowest one from which a dropped egg
breaks.  From now on, we'll call it the "break point".  This implies, of
course, that the (n-1)th floor is the highest one from which a dropped
egg doesn't break.

Considering all possible cases, the minimum number of trials that leads
to a conclusion is, of course, 1.  If the "break point" is the 1st floor
and you choose it as your first try, you'll have solved the problem.
But this is the most favorable situation.

"The least number of drops", as stated, means that we're looking for a
number of trials such that, even in the worst case, we'll get the
problem solved.

With this in mind, let us suppose that we are given a certain number of
trials to solve the problem, say, for instance, 11.  It is then clear
that our first attempt can't be done from a higher floor than the 11th.

Why is that?  Well, imagine that we try a drop from the 12th floor and
the first egg breaks.  Now, the only possible way to determine the
"break point" is to throw the second egg from the 1st floor, then from
the 2nd, then from the third, etc, until it breaks (if it doesn't as far
as the 11th floor, the "break point" will be the 12th).  In the worst
case, it will cost us 1+11=12 tries to solve the problem, which exceeds
our limit.

Now, suppose that the minimum of tries that solves the problem is x.

As seen above, the first try must be at most from the xth floor.  Let us
use this xth floor.  If the first egg breaks, we'll make, in the worst
case, (x-1) more trials to solve the problem.  So, we'll have made
(x-1) + 1 = x trials at all.

What if the first egg doesn't break?  Well, then our next try must be at
most (x-1) floors above.  If the first egg breaks at this [x + (x-1)]th
floor, the only possible way to handle the situation is to drop the
second egg from (x+1)th floor, then from the (x+2) floor, etc.  In the
worst case, we'll have done [1 + 1 + (x-2)] = x attempts.

At this point, we can deduce that if the first egg doesn't break at
[x+(x-1)]th floor, our next trial will be, at most, (x-2) floors above.
Continuing, and always thinking about the worst case, we must reach the
36th floor in our last attempt.  In other words, it comes:

x + (x-1) + (x-2) + ....+ 1 = 36

The left part of the equation is the sum of the x first natural numbers,
which is equal to x(x+1)/2.  Then,

x(x+1)/2 = 36   ==> x^2 + x - 72 = 0

The positive solution is then 8.

So, the first attempt will be done at the 8th floor.  If the first egg
breaks, we'll drop the second egg from the 1st floor, then from the 2nd
and so on, until it breaks (if the egg doesn't break at the last
attempt, say the 7th floor, the "break point" will be, of course the 8th
floor).  If the first egg doesn't break, then we'll try the 8+7 = 15th
floor.  Now, if the egg breaks, we'll try the 9th floor, then the 10th
and so on; if it doesn't, our next trial will be at the 8 + 7 + 6 = 21st
floor.  And so forth.

Finally, and since our first attempt could be at most from the xth
floor, one can ask why didn't we try a lower floor.  Well, if the first
egg breaks when dropped from this lower floor, we would have to make a
less number of trials to get to a conclusion.  But if not, we would have
to face a worse situation.  We would also have (x-1) attempts left, but,
at this point, the number of remaining floors to investigate would be
greater.  So, it is obvious that the quickest way is to drop the first
egg from the xth floor.  This is also true in all other situations in
which the expression "at most from the nth floor" appears.

-- Paulo Roberto Pereira Lagreca <lagreca@horto.rjo.serpro.gov.br>

[ Editor: the same problem with glasses and a 100-storey building,
rec.puzzles, November 1997. ]

Danny Hendler (dannyh@taux01.nsc.com) wrote:
: You have 2 glasses and a 100-storeys building. Both glasses are of
: the same quality, such that they break when you throw them out
: of the window of a certain storey - say X - and upwards, but not
: if you throw them from storeys 1..(X-1).
:
: You have to find this X, and you have to do it with a minimal
: worst-case number of throws. (Needless to say, after a glass is
: broken, it is useless.)

For the 100 story case it is possible to find X with 14 drops.

Find the smallest triangle number larger than 100.  It's 105 which is
1+2+...+14.  So start by dropping the first glass from the 14th floor.
If it doesn't break go up 13 floors to the 27th.  Then go up 12 floors,
11 floors, etc.  Once the first glass breaks go back down and work your
way up floor by floor.

-- Kevin D. Green <kdg977t@cnas.smsu.edu>