Article: 26224 of sci.math
From: torbenm@diku.dk (Torben AEgidius Mogensen)
Date: Thu, 27 May 1993 11:01:55 GMT
Organization: Department of Computer Science, U of Copenhagen

jhusdhui@math.tau.ac.il (Gurel-gurevitch Ori) writes:

>OK, so here's two nice problem for the enjoyment of the net:
>1)suppose you have two eggs and one 100 floors tower. you want
>  to know which floor is the critical one, i.e. below that floor
>  the eggs will survive the fall and above this floor (inclding)
>  the eggs will crash. find an algorithm  to do this with 
>  minimal number of throwings in the worst case. remember you
>  have only two eggs to crash.
>  can you generalize the result to any number of floors? to any
>  number of eggs? both?

Choose a number t, then throw an egg from floor t, then 2*t-1,
3*t-2,...  until it breaks or n*t-n+1 is greater than 99. If the egg
breaks, throw the other egg in 1-floor steps from the last floor the
first survied until it breaks or survives the floor just below where
the first breaks.

The idea is that the sum of throws you make with the first egg (n) and
the max number of throws you must make with the second egg (t-n) is
constant (t). If t is chosen as the smallest number such that
1+...+t >= 100, then this gives the minimal number of worst-case
throws (t). So we must solve t*(t+1)/2 = 100, and round up.
This gives t=13.65 and thus a maximum of 14 throws.

The exact procedure for 100 floors is:

1) Throw from floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100

2) If the first egg breaks at floor 69, drop other egg from floor
   61,...,68. This generalizes to breaking at other floors.

If there are N floors, you must solve t*(t+1)/2 = N, which gives t =
(sqrt(8*N)-1)/2 (rounded up).

This gives the following table of maximum size of building that can be
solved with t throws.

t	1  2  3  4  5  6  7  8  9 10 11 12 13  14  15  16
floors  1  3  6 10 15 21 28 36 45 55 66 78 91 105 120 136

If you have 3 eggs, you must use the first to divide the tower into
segments that can be solved by the other two eggs. Again the number of
throws by the first eggs plus the number of throws to solve the
segment must be constant. So in the first segment you have u-1 throws
with the last two eggs, in the next you have u-2, then u-3 etc. Again
we aim for the number of segments being close to u. So for u=5 we have
4 throws for the first segment giving 10 floors in the first segment
(excluding the endpoints), 3 throws for the next segment giving 6
floors, then 3 floors and finally 1 floor in the last segment. This
adds up to 5+10+6+3+1=25 floors with 5 throws. So you throw the first
egg from floors 11, 18, 22, 24, 25. If it breaks at b, you solve that
segment using the two-egg algorithm for (b-a-1) floors, where a is the
floor tried before b.

In general, with u throws you can solve up to

u+ (1*2/2+...+u*(u-1)/2) = u+ (u^3-u)/6

floors, which gives the following table

u	1  2  3  4  5  6  7  8   9  10  11  12  13  14  15  16
floors  1  3  7 14 25 41 63 92 129 176 231 298 377 469 575 696

This idea can be generalized to more eggs: use the first egg to divide
into segments, each of which are solved using the algorithm for n-1
eggs. I can't offhand find a closed form formula for finding the
number of floors from the number of eggs and throws.

Of course, one could say that the answer is that an egg breaks when
thrown from the first floor regardless of the size of the building.
But I guess this isn't the answer the poster wants.

	Torben Mogensen (torbenm@diku.dk)