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)-
Subj:     MATH PROB. - Three Eggs & A 1000 Story Building (S387b)
          From: 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)-