0809.7: Solution


Puzzle #7: Egg-Drop Soup (May 2009)

The Puzzler’s Solution

             The answer for the twenty-one step puzzle is six. Start at the sixth step. If the first egg breaks, go to the first step and drop the other egg, increasing one step at a time until it breaks. If the egg does not break on the sixth step, go to the eleventh step. If it breaks, start at the seventh step, increasing one step at a time. If the egg does not break on the eleventh step, go to the fifteenth; then the eighteenth, twentieth, and twenty-first steps. Here’s a diagram:

 

eggdiagram.gif

 

Start at step 6, and follow the single arrows down the top of the diagram until the first egg breaks. Then, move SW in the diagram along the double arrow. One the first egg breaks and you are in the lower part of the diagram, proceed down the column until the second egg breaks. That’s the solution, and you can break the rest of the eggs.

The bonus challenge was to find a formula to determine, for any number of steps, the fewest number of drops you might have to take to discover the lowest step from which the eggs break. Constructing diagrams similar to the one above, I noticed that the maximum number of steps you could test was always the sum of the integers from one to the number of the starting step. And, the starting step was always the maximum number of drops that you would have to make. So, if you started on the fourth step, you could test up to ten steps, since 1+2+3+4=10. Here is a chart:

 

Starting at step...

you can test up to this many steps:

1

1

2

3

3

6

4

10

5

15

6

21

7

28

 

Since the sum of the integers from one to n is n(n+1)/2, the following inequality holds, for any number of steps s:

             n(n+1)/2 > s

Expanding this inequality, and using the quadratic formula, I arrived at the following solution for the starting step n, given a number of steps s:

             n must be the least integer greater than or equal to (-1 + sqrt(1+ 8s))/2

 

 

An Alternate Method

An solution from JL (who describes him/herself as an ex-Clinton Townie) included a slightly simpler formula, and an excellent derivation. Here is the formula:

s must be the greatest integer less than or equal to ½ + sqrt(2n)

Here is the derivation of the formula, in JL's words:

assume only two steps.  we drop an egg from the first step; if it breaks, the first step is the correct height.  otherwise, the the second step is the correct height.  thus, for two steps, one drop is sufficient; i.e., f(2) = 1.

now, assume the problem is solved for stairs with less than N steps and we need to solve for N steps.  the first drop is made from the f(N-1)th step.  if the first egg breaks, we then drop eggs from the stairs in order, starting from the first, until another egg breaks or we have dropped from the step below the first drop; i.e., f(N) = f(N-1).  if the first egg does not break, the problem has been reduced to the N-f(N-1) case with the addition of an extra drop: i.e., f(N) = f(N-f(N-1))+1.

so, between the two choices, f(N) = max( f(N-1), f(N-f(N-1))+1 ).  the latter term is a recurrence relationship which can be expressed by the following simple formula: f(N) = floor( 1/2 + sqrt( 2N ) ).  [REF1]  this formula is monotonically increasing; therefore, when compared to the former term (constant), it will always be at least as big.  thus, we can reduce our equation to f(N) = f(N-f(N-1))+1, e.g., f(N) = floor( 1/2 + sqrt( 2N ) ).