| 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
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
 |
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:
Additional
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======================
 |