Puzzler -- Egg Drop

Re: Puzzler -- Egg Drop

Bill Earl

Sounds like what I did to my omelet this morning

Alex Y

Took me a while to see your answer, but the teacher can make it more restrictive than eight tries.

Unless you were answering the P.S.

Re: 

Larry Barrett

Maybe what Bill meant was that he made it by hand.

  Maybe so

Alex Y

Sounds like you are onto something there! Care to post your method?

Re:   Maybe so

Larry Barrett

The basic rule to follow is this: As long as you have more than one egg left, use them to reduce the possible answer range by half. When you have just one egg left, start at the bottom of the range and work your way up.

So, with three eggs, drop one at 12”. If it breaks , the second egg at 6”. If the first does not break at 12”, drop it again at 18”. So after 2 drops, you have reduced the answer range to explore to these possibilities:

19-24 with 3 eggs left; 13-17 with 2 eggs left; 7-11 with 2 eggs left, and 1-5 with 1 egg left.

For the first three cases, with 2 or 3 eggs left, drop an egg at the mid-point, for example for case 1, drop at 21”. If it breaks, drop another at 19; it this one breaks, then the solution is 18”; if it does not break at 19 then drop at 20”; the solution will be either 19 (if it breaks at 20), or 20, if it does not break. For this case, a solution was found with 4 or 5 drops. A similar analysis will show that 4 or 5 drops will find a solution for the first three cases where there are 2 or 3 eggs remaining after the first 2 drops. For the last case, where the answer range is 1-5 and there is just I egg left, you have to start at 1 and work your way up. If the solution turns out to be 4 or 5, it will take 6 or 7 drops to find it.

A similar analysis applied to the PS problem (range of 200 with 5 eggs) will show that if the first drop at 100 does not break, a solution can be found with 8 drops. In the worst case, where the egg breaks at each mid-point (100, 50, 25, 12) I think if could take up to 16 drops to find a solution.

  Not there yet

Alex Y

I misinterpreted your "by hand" comment. It looks like your solution requires seven drops in the worst case. The correct answer is less than that. And for the PS version, the right answer is surprisingly much less than the 16 you speculated.

Suggestion

Alex Y

Larry said:

The basic rule to follow is this: As long as you have more than one egg left, use them to reduce the possible answer range by half.

The "reduction of possible answer ranges" approach is right, but why separate the possibilities in half? If the egg breaks on the first trial, you have two eggs left to test all lower levels, while if it doesn't break, you have three eggs left to test the higher levels.

Dropping the first egg at 12" led to more trials needed when the "breaking point" was at a low height.

Re: Suggestion

Ed in Leaside

I had guessed the first drop would be at 8".

Re: Suggestion

Alex Y

First drop is > 8 and <12

Hint

Alex Y

Work backwards. Figure out the number of levels that can be completely determined for a given number of drops and eggs.

Re: Hint

Larry Barrett

If first drop is at 11, then possible sequences are

11,4,1,2,3

11,4,7,5,6

11,4,7,9,8

11,4,7,9,10

so max 5 drops for this range, and we already know max 5 drops for 12-24, so "by hand" makes sense now.

I don't see the logic for start at 11 yet, so can't extrapolate to the PS case.

  Correct

Alex Y

Congrats, Larry;

The teacher can indeed allow as few as five drops, and the students can still test all possibilities.

Here are the complete decision paths:

As you see, it is actually possible to test 25 levels with only three eggs and five drops. In the chart above, "level" is the number of inches from which an egg can be dropped without breaking. The yellow boxes indicate a broken egg on that trial (a little yolk there).

I'll leave open the "why" of the 11" first test and the general approach for a few days if anyone wants to keep working at that.

Solution -- general case

Alex Y

As mentioned in the hint, we need to work backwards. If we can find the number of levels that can be distinguished for a certain number of eggs and drops, we just need to find the smallest number of drops that with three eggs lets us distinguish at least 24 levels.

For those of you who like variables and functions, lets call L(d,e) the number of levels that can be distinguished by d drops of e eggs.

If we have e eggs and d drops, the first thing we need to do is drop an egg from some level.

If it breaks, we know that the maximum level is below the one from which we dropped it. But after that, we have e-1 eggs left and d-1 drops left, so the most we can distinguish is L(d-1,e-1). So our original drop point should be at L(d-1,e-1)+1.

If it doesn't break, we have used up one of our drops, but not an egg, so we can distinguish L(d-1,e) levels above the drop point.

This gives us an iterative formula for L:

L(d,e)=L(d-1,e-1) + 1 + L(d-1,e)

The starting points for this iteration are easy: If you only have one egg, you have to start at 1" and increase 1" at a time until the egg breaks, so L(d,1)=d for any d. If you only have 1 drop, it doesn't make any difference how many eggs you have, you can only test the first level, so L(1,e)=1 for any e.

That lets us easily generate a table like this:

Following down the columns, you can see that for three eggs, it takes five drops to distinguish at lest 24 levels. The first drop is a L(4,2)+1 = 11. For five eggs, it takes at eight drops to distinguish at least 200 levels.

Note also that when e >= d, L is 2^d - 1. Sounds like a binary number with bits represented by eggs! And this says that without the restriction caused by a limited number of eggs, you just keep dividing the possibilities by two.

Re: Solution -- general case

Larry Barrett

Neat! but how did you know to start at 11? and where do you start with 5 eggs?

Re: Solution -- general case

Alex Y

how did you know to start at 11?

Once we know that 5 drops of 3 eggs will do the trick, we look at what happens after the first drop. If the egg breaks, that leaves us with 4 drops of 2 eggs to distinguish all of the levels below the drop point. From the table, we see that L(4,2) = 10. If we drop above 11, we won't be able to distinguish all of the lower levels, while if we drop at 10 or lower, we are "wasting" some of our ability to distinguish with 4 and 2.

and where do you start with 5 eggs?

For 8 drops with 5 eggs, we start at L(7,4) + 1 = 99