Friday Puzzler--Testing packaging, v2

Hint

Alex Y

There is no requirement that the first egg be dropped from floors that increase the same amount each time.

Re: Hint

Ed in Leaside

So first drop is from ten ...

Re: Hint

Larry Barrett

I am not sure which puzzle I am solving, but ...

Start at floor 11. If egg breaks, test floors 1 - 10; total max drops = 1+10 = 11.

If egg does not break at 11, go to floor 21 (plus 10). If egg breaks, test floors 12 - 20; total max drops = 2+9 = 11.

If egg does not break at 21, go to floor 30 (plus 9). If egg breaks, test floors 22 - 29; total max drops = 3+8 = 11.

If egg does not drop at 30, go to floor 38 (plus eight). If egg breaks, test floors 31-37; total max drops = 4+7 = 11.

If egg does not break at 38, go to floor 45 (plus 7). If egg breaks, test floors 39 - 44; total max drops = 5+6 = 11.

If egg does not drop at 45, go to floor 51 (plus 6). If egg breaks, test floors 46-50; total max drops = 6+5 = 11.

If egg does not break at 50, test floors 52, 53, 54, 55. Total max drops = 6+4 = 10.

So overall max drops = 11.

Re: Hint

Alex Y

Ed, I suspect you may have the answer, although that ellipsis does cover quite a bit! ;-)

Just to confirm that you have the answer, if the first egg is broken on its fourth drop, what is the first floor you then drop the second egg from?

Re: Hint

Alex Y

I am not sure which puzzle I am solving, but ...

Fair enough, Larry. I should have posted this hint on the first version of the puzzle as well, and your answer tells me that you are working on that harder one.

Your approach is right, but you haven't pushed it quite far enough.

Re: Hint - pushing further ...

Larry Barrett

Start at floor 10, as Ed says.

If first egg does not break, move up to floor 19, then 27, 34, 40, 45, 49, 52, 54, 55.

If first egg does break at any of these floors, then go back to last success +1.

Max drops: 1+9, 2+8, 3+7, ... 8+2, 9+1, 10+0 = 10.

Re: Hint

Ed in Leaside

Larry has it at 28.

Correct!

Alex Y

The next hint was gong to be "10*11/2 = 55" ;-)

Correct!

Re: Correct!

Larry Barrett

I thought about that - "what's special about 55?". But still did not get any insight into this one. Can it be generalized in some way? What if you had 3 eggs to break instead of two?

Good question

Alex Y

I think it can be generalized, but gets ugly with more eggs. For three eggs and n drops, I think you can test up to:

n+sum from 1 to n of (x-1)(x)/2

so with 6 drops, you could test up to a 41 story building.

For an arbitrary k eggs? I don't know.

Re: Good question

Larry Barrett

I don't know how to express this as an equation, but I think the process is this:

If you have x eggs and are allowed n drops, you start with the first egg at a floor 1 higher than the highest you can go with x-1 eggs and n-1 drops. If the first egg breaks, then you can test up to that floor with the x-1 eggs. If the first egg does not break, move up the number of floors that you can test with x-1 eggs and n-2 drops, plus 1. Continue in this manner.

So, in your example, with 3 eggs and 6 drops, start on the 16th floor, because if it breaks, you can test up to 15 floors with 2 eggs and 5 drops (5x6/2). If the first egg does not break, move up 11 floors to the 27th floor, because you can test 10 floors with 2 eggs and 4 drops (4x5/2). If the first egg does not break, continue moving up to the 34th floor, then 38th floor, and the 40th floor (which would be the 5th drop); and with the remaining 1 drop you can test first floor 39, then floor 41.

Very clear

Alex Y

I hadn't thought of it this way.

Thanks.