Friday Puzzler -- Testing Packaging

Re: Friday Puzzler -- Testing Packaging

Ed in Leaside

I think 28.

No, that's not it ...

Re: Friday Puzzler -- Testing Packaging

Larry Barrett

How about 18. Start at the 3d floor.

Re: Friday Puzzler -- Testing Packaging

Alex Y

Not sure what you are proposing after starting with the third floor.

It can be done in fewer tests.

Re: Friday Puzzler -- Testing Packaging

Henry Higginbotham

I think it could be done with six drops, or maybe five (it's still Before Coffee here). A Yes/No flow chart starting at the 27th floor and then moving halfway to the 55th floor (if it breaks) or to the 1st floor (if it doesn't) and adjusting in the same manner for successive yes or no results, appears to conclude after no more than six drops.

But the wording of the puzzle seems to indicate it might be done with two eggs. I think I'll go make some coffee.

Only 2 eggs

Alex Y

and no, you can't determine the highest floor with only 6 drops.

Re: Friday Puzzler -- Testing Packaging

Larry Barrett

My thought was to start at the 3rd floor. If that egg does not break, go to the 6th floor. Continue by 3 to the 54th floor. If the egg breaks at any floor, go down one floor and drop the second egg. The answer would be that floor or the one below, depending on whether the second egg broke, or not. If the drop at the 54th floor did not break, then drop the second egg at the 55th floor. So a total of 18+1 drops.

Since you say it can be done with fewer drops, I need to put Humpty Dumpty together again.

Re: Friday Puzzler -- Testing Packaging

Alex Y

You are on the right track, with the first egg drop narrowing the range that needs to be tested with the second egg.

In the every third floor approach, if the egg does not break on the nth floor, but does break when dropping from n+3 and the second egg breaks when dropping from n+2, you will not know if the highest floor is n or n+1. So the second egg may need to be dropped twice, from n+1 and from n+2, so potentially 20 drops.

Re: Friday Puzzler -- Testing Packaging

Gary Smyth

Given the eggs are identical and can be reused. I can do it in maximum 9 if I start at floor ten and go up 10 floors each time until the egg breaks. That's egg one. I can then go to the second egg. Going down to the last multiple of ten where the egg did not break, go up two floors each drop until it does and that is the number -1. Possible 9 drops.

Egg 1 does not break at 55. Maximum six drops. Below floor 55 say floor 50 there are five drops and by going to the last floor multiple of 10 where the egg did not break and going up two floors there is a maximum of four drops --say 32, 34, 36, 38. The maximum is, by my logic, nine drops

Previous should read floor 30 not 50

Re: Friday Puzzler -- Testing Packaging

Alexy

Gary,

If you drop the package with the first egg five times and it breaks on the 50th floor, then you drop with the second egg from 42, then it breaks at 44, what is the highest floor from which it wouldn't break? Without dropping from 43, how could you tell whether 42 or 43 is the highest floor?

Dropping the second egg every floor gets you a solution with 14 drops. Good, but not optimal.

clarification

Gary Smyth

If the egg breaks at floor fifty that's five drops. You already know that the egg did not break at drop forty so you drop at floor 42. If it breaks at 42 then you know 41 is the number. Continue on by twos. If the egg does not break at floor 48 but does break at fifty which you already know, the floor is 50, -1 or floor forty nine. For a fifty story building the maximum would be floors (10-50) 5 + 4 = 9. For 55 story building the maximum wound be floor 10 through 50 = 5 drops. If the egg is still intact at floor fifty then the maximum would be floor 50 = five drops, plus floor 52, 54. If it breaks at either of those floors, that is the number -1.. If the egg is still intact at 54 (after seven drops) then the number is 55 which is still a maximum of seven drops. If the egg doesn't break at floor 54 the number is 55. That has to be the number because the building doesn't go higher. If the egg is good at fifty and going up by two stories each time the maximum number of drops would be seven. 5 stories (10-50) plus 52, 54. If the egg breaks at 54 you know the number is 54-1 or 53. The number of drops is possibly greater on the lower floors because the floor multiple is 10 (20 to 30, 30 to 40, etc.) On the lower floors there is the possibility of four drops (example 42,44,46,48) At floor fifty the multiple is five because the building only goes to 55. Not 60, or more. By my method I can't get to 14 drops unless the original number of floors is larger than 55. As Randy Newman wrote in the old Monk opening theme. " I may be wrong now, but I don't think so."

Does it break on an odd floor?

Alex Y

Gary, you said:

If the egg breaks at floor fifty that's five drops. You already know

that the egg did not break at drop forty so you drop at floor 42.

If it breaks at 42 then you know 41 is the number.

How do you know that 41 is the number and not 40? It might have broken if you had dropped from 41.

Re: Does it break on an odd floor?

Gary Smyth

The question. What is the smallest number of egg drops must they make in order to be assured of finding the highest floor their packaging provide protection from?

As I understand the question you asked for the smallest number of drops. I estimated the maximum number of drops up to floor 55. It could be fewer depending on the floor of failure.

To use your example. Floor forty has been cleared but not fifty. One egg down. Five drops.

I go back to floor 42. If the egg breaks at that floor, the answer is average 41. However floor 42 is for certain is failure. The egg was OK at 40 but failed at 42. It may have failed at 41 or 42 but either floor is one drop. That would be five drops plus one = six. Floor 41 or floor 42 is irrelevant if we are counting drops and assured safety of the egg. In a 55 floor building the maximum number of drops number of drops for the range 1-48 is nine drops 1-50 (five drops) and max 42,44, 46, 48. (four drops). If the first egg survives to floor 50 the max would be five drops plus 2 (52, 54) =7

I was incorrect about identifying a specific floor, but I believe correct in a drop number to assure success of the packaging.

Re: Friday Puzzler -- Testing Packaging

Larry Barrett

Gary has a good idea of going up by a large number of floors (10 in his example) until the first egg breaks. But then it seems like you have to go back to the last successful floor and go up one at a time until the second egg breaks. So in Gary's example it seems to me that the max number of drops for the first 50 floors would be 5+9=14. The second check is to find the number of drops if the first egg is successful at the largest number of drops below 55, in Gary's case floor 50. So here you must continue testing floors 51, 52, 53, 54, 55. So the max here would be 5+5=10. So the overall max is 14.

Since you must test 9 floors in one case or 5 in the second, there might be a better optimum number of floors to jump with the first egg, so that the second series of drops is the same whether the first egg fails at the highest floor, or not.

Seven seems like a good solution here. This would take 7 drops with the first egg to get to floor 49, and 6 additional drops with the second egg to confirm a floor between the last successful drop and the first failure of the first egg, or 7+6=13 drops if the first egg fails at the 49 floor. And if the fist egg does not break at the 49 floor, then an additional drop at 50, 51, 52, 53, 54, 55 - 6 more drops so the max is again 7+6=13.

The best so far

Alex Y

But still not quite optimal

Re: The best so far

Larry Barrett

With enough hints we might stumble onto the answer,

How about if, within the 'jump' interval (10 for Gary, 7 for me) you then test by 2. If success, go up by 2, if fail, go down 1.

For example, in Gary's answer, test by 10 up to 50 (5 drops). Then if fail at 50, go back to 42. If success, go to 44; if fail at 42, go to 41. If success at 41, then 41 is the answer; if fail at 41, then 40 is the answer. So go up by 2 - 42, 44, 46, 48; if fail at 42, 44, 46, 48 then go down 1. If success at 48, go up 1 to 49. So this adds a max of 5 more drops, for a total max of 5+5=10 if there was an intitial fail at 50.

If there was success at 50, then go up by 2 (52, 54) and if fail at either, go down 1. If success at 54, go up 1 to 55. So the max in this case is 5+3=8, so overall max is 10.

In my answer, go up by 7 to 49, then if fail at 49 go back to 42+2=44 and test at 44, 46, 48. If fail at any, go down 1. So max here is 7+4=11 - already more than Gary.

Checking a jump of 11 seems to yield a max of 5+6=11.

A jump of 12 seems to yield a max of 4+6=10.

So it looks to me like the max is 10 and there seems to be more than one way to get there.

Whoops!

Alex Y

"For example, in Gary's answer, test by 10 up to 50 (5 drops). Then if fail at 50, go back to 42. If success, go to 44; if fail at 42, go to 41"

If you fail at 42, you've used up your last egg, so there is no testing of 41

Good point - back to drawing board

Not to belabor the point but....

Gary Smyth

You asked what floor is assured safety by the number of drops.

"What is the smallest number of egg drops must they make in order to be assured of finding the highest floor their packaging provide protection from?"

In my reading odd number of the floor of 41 or even 42 is not the question. The question is number of drops to be assured of safety. As I understood the question the question was drops not floor. To be assured, by my figuring, a failure of the second egg at 42, but a success at floor 40 is the same number of drops.

No harm no foul. I'll look forward to your answer for your response to the question

Re: Not to belabor the point but....

Alex Y

Clearly I haven't communicated this well enough.

We want to find the highest floor from which the packaging provides safety. E.g., it might provide protection up through the 33rd floor, but not above. Or it might provide protection up through the 46th floor, but not above.

We want to determine a scheme to find that floor (33 or 46 in the examples above) in as few drops as possible.

As I understood your approach, you would always drop the package from even numbered floors, and say that the highest safe floor was 1 less than the last break floor. Since you are only dropping from even numbered floors, you will always say that the highest safe floor is an odd numbered floor. For packaging that is only good through the 46th floor, you will find that the second egg breaks at 48, so say the packaging is good through the 47th floor.

At least, that is my reading of the approach you suggested.