The Hamilton Puzzler The Continental Conundrum The Befuddled Blue

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

Click to go to:

The Puzzle

The Puzzler's solution

An Excellent Alternate Solution, from someone self-described as an ex-Clinton Townie

Have a nice summer!

To celebrate the end of classes (and our final puzzle of the year) the physics department is planning to make their famous egg drop soup. To make egg drop soup, you have to break eleven eggs by dropping them from the lowest step between the first and second floors of the Science Center which will cause them to break. If you drop an egg from too low a step, the egg will not break. If you drop an egg from too high a step, the soup will be ruined. There are twenty-one steps.

Here are some more guidelines: If an egg does not break, it can be re-used. If one egg breaks, or fails to break, from a given step, then all the other eggs will do the same. If an egg breaks when dropped from a given step, then all eggs will break when dropped from all higher steps. If an egg does not break when dropped from a given step, then all eggs will not break when dropped from all lower steps.

The physicists have a dozen eggs. If they needed the whole dozen for the soup, they would have to start at the first step, dropping an egg at each step until it broke. Once they reached the lowest step at which the egg breaks, they would drop the rest of the dozen, scrape them from the floor, and make the soup. This procedure might require as many as 21 egg drops.
But, they only need eleven eggs.

Question

What is the fewest number of drops that is guaranteed to determine the right height from which to drop eggs, and which will lead to yummy egg-drop soup? Solutions must include an explanation.

Bonus Question

Can you generalize the result to n steps?

Go to the Puzzler's solution, an Alternate solution, or the Top

The Puzzler's solution:

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:

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:

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

Go to the Puzzle, an Alternate solution, or the Top

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 ) ).

 

Go to the Puzzle, the Puzzler's solution, or the Top