Subj:     MATH PROB. - Two Eggs & A 100 Story Building (S381b)             From: jimmysu on 5/9/2004   You have a 100 story building and two eggs.  These are   especially strong eggs.  There is some floor below which   the egg will not break if dropped.  What is the worst case   upper bound on the number of drops you must make to  determine this floor?   THE SOLUTION (Done by my Cousin Ron and me)

Let N the number of drops you need to find the first floor
that breaks eggs.  Go to the Nth floor and drop an egg.  If
it breaks you have N - 1 more drops to test the N - 1 floors
below.  If it doesn't breaks, go to the N + (N - 1) floor
and drop the same egg.  If it breaks you have N -2 drops
left to test the N - 2 floors between Nth floor and 2N -1
floor.  By a similar analysis you approach the top of the
building with

N + (N - 1) + (N - 2) + (N - 3) + . . . + 1 <= 100

N ( N + 1 ) / 2 <= 100

This is a quadratic equation which yields N <= 13.65.  If
N = 13 you can only analyze a building of 91 floors.  It
takes N = 14 to test a 100 floor building.

Final solution.  You go to the 14th floor and drop an egg.
If it breaks you have 13 more drops to test floors 1 to 13.
If it doesn't break you go to the 27th (14 + 13) and drop
the first egg again.  If it breaks you have 12 drops left
to test the 12 floors above 14 and below 27.  You continue
up the building until you reach the 99th floor
(14+13+12+11+10+9+8+7+6+5+4) with three drops left.  If it
breaks you have three drops left to test the three floors
between the 95th floor and the 99th floor.

Jimmys Su's more exact solution is
\\\//
-(o o)-
========================oOO==(_)==OOo======================
Subj:     MATH PROB. - Three Eggs & A 1000 Story Building (S387b)
From: jmholmes@sbcglobal.net on 5/9/2004

During the solution of the math problem "Two Eggs & a 100
Story Building" in Sunday Morning Laughs #381b, I challenged
the readers to the next level problem:

You have a 1000 story building and three eggs.  These are
especially strong eggs.  There is some floor below which
the egg will not break if dropped.  What is the worst case
upper bound on the number of drops you must make to
determine this floor?

THE SOLUTION (Done by Jack)

First let me say I've yet to read the answer for the 2 egg
and 100 story building, so I must share how I got to my
solution:  Before I try to turn something I've not seen
before into an equation I like to play with it a bit.  In
this case I looked at the normal binary approach and saw
the general situation that once the egg breaks you must
deal with all the unknown floors one at a time, and so the
rate that you climb the building must be balanced against
the drops required to fill in the gap.  Another sampling
at 10 floors per drop made it clear that the optimal rate
also depended upon the height of the building.  Since the
height was reduced with each drop, I prepared to solve it
recursively when the answer leaped out at me.  With a known
optimal number for a particular height the next lower height
must require one fewer drops, since to get to that lower
height you've taken one drop.   At the limit of a one story
building it takes one drop.  As you increase the height,
adding one drop each time, it's obvious that this allows a
one floor increase in the climb rate.  Thus a 100 story
building has a minimum of 14 drops - the first number where
the summation exceeds 100.

With a 1000 story building and three eggs the approach is
the same:  You want a climb rate that reduces the required
number of drops by one each time you take a drop until you
reach the lower limit.  It seems clear (I wish I could tell
you why it's clear - this is why I could never be a teacher)
that the step rate will be equal to the summation.  The sum
of the sums that is equal to or more than 1000 is for n = 18
(it's actually the sum of the sums plus n).  So the answer
is 19 drops:

Two Egg           Drops if
Drop    Building           Egg Breaks            Total
Floor     Height          (2 Egg Solution)       Drops
172         171              18                    19
326         153              17                    19
463         136              16                    19
584         120              15                    19
690         105              14                    19
782          91              13                    19
861          78              12                    19
928          66              11                    19
984          55              10                    19
1030          45               9                    19
1067          36               8                    19
1096          28               7                    19
1118          21               6                    19
1134          15               5                    19
1145          10               4                    19
1152           6               3                    19
1156           3               2                    19
1158           1               1                    19

Jack, you solution is correct, clear, and the first solution.

\\\//
-(o o)-
========================oOO==(_)==OOo======================