1. Pathways
  2. Freedom and Constraints
  3. Making Life Easier
  4. Dropping Eggs

Dropping Eggs

Dropping Eggs
Imagine you make egg-shaped ornaments, and you want to tell customers how high the eggs can be safely dropped from, without breaking them!

If you had an egg to test by dropping it from each floor of a 100 storey building, you'd need to start by dropping it from the first floor, and if it didn't break, go up to the second floor, and if it didn't break, go up to the third floor...

In the worst case scenario, you might have to do 100 tests to find out where it breaks!

It would speed the process up if you had two eggs...

How would you use the extra egg so that you don't need to do so many trials?

Perhaps you might drop the first egg from the 5th floor. If it breaks, use the second egg to test floors 1 to 4.

If it doesn't break, drop the first egg from...

 

Can you come up with a strategy, using two eggs, to minimise the maximum number of trials you might have to do?

What if there were more floors?

What if you had more eggs?

You may want to use a spreadsheet or write a simple program to tackle parts of this problem.

 

Comments

Submitted by Derrick on Tue, 11/17/2015 - 01:06

If you have 2 eggs you could drop it every 10 layers: you go from 10 and go up 10 every time. When 1 egg finally breaks, you can go from 10 lower than the one where it breaks and add 1 until it breaks and minus 1 to get how high the eggs can be safely dropped from.

If there were more floors, you could make it going up 20 every time.

If you had more eggs you could make it more quickly by making it go up by 20. Then you minus 10 and you drop an egg at that level. Now you would know if it's above that level or below and just add 1 every time.

Submitted by dp419 on Tue, 11/17/2015 - 11:57

This is a really good strategy; can you work out the maximum number of drops that this might require?

Can you (or anyone else) find a strategy that is even better than this one? Or is this the best one possible?

Submitted by Derrick on Tue, 11/24/2015 - 01:54

The maximum number of drops would be 9 (Dropping on every 10th floor to the 90th) then +10 (1 floor every time to 100), so the most drops you could have is 19 if the total number of floors is 100, since 10+9=19. If you put it on 100 the second time, it would be too risky.

If you had 3 eggs, you could drop every 20 floors, then you could drop an egg at the floor ten lower than this, and then use the final egg to go up the ten floors one at a time. This would require at most 5 drops (every 20 floors up to 100), (then you drop a egg at 90) +1, and (1 floor every time to 99) +9 . 5+1+9=15. You couldn't put it to 100 because you have 3 eggs and you wouldn't lose all your eggs.

Submitted by dp419 on Tue, 11/24/2015 - 10:06

I agree that your method should take at most 19 drops to find the limit of where the eggs can be dropped from. Well done! Can anyone do even better than this?

Your strategy for three eggs is also very good! Can you make it even better?

Submitted by hash on Tue, 02/02/2016 - 14:22

The minimum number of drops would be 8, but I would need 8 eggs for that.

I would go first to floor 50, and drop an egg. If it breaks, I would know the solution is somewhere among floors 0-49, if not, then I would test for floors 51 to 100. Then I would go to floor 25 (or 75, depending on the first outcome) and drop another egg. And so on.

I could break all 8 eggs (floor 0) or none (floor 100).

ajk44's picture

Submitted by ajk44 on Mon, 02/08/2016 - 10:57

I like your solution needing many eggs. This sort of a solution is known as a binary search - can you work out how many eggs you would need to use your method for 200 floors? Or 1000 floors? Or...

Can you find a strategy that doesn't require so many eggs?

Submitted by Aryan on Sun, 09/25/2016 - 13:51

you only need two eggs, you go up in 5's once it breaks you go back 4 and then when it brakes you know the durability

Submitted by Steven on Sun, 02/07/2016 - 21:06

For two eggs we are looking for the maximum number of drops for 100 storeys.
Drop every ten floors. If egg broke on 10, then need 9 more trials at most to figure out which floor it breaks on 1+9 =10 trials.
If didn't break on 10 but broke on 20th floor requires 9 more trials at most 2+9 = 11 trials
Proceeding in the same way to 90th floor. If it broke on 90th floor then max trials is 18 trials.
BUT IF IT DIDN'T break on 90th floor we still have 2 eggs and have only dropped 9 times so far. We can do something different for the remaining floors.
Drop from 95th floor (10th trial) if breaks we have 4 more trials at most (91st, 92nd, 93rd, 94th) for a total of 14 trials.
IF it didn't break we still have 2 eggs and have only done 10 trials with 5 floors remaining to test (96, 97, 98, 99, 100).
Drop from 98th floor (11th trial). If it breaks then at most 2 more trials for a total of 13 trials.
If it didn't break we still have at most 2 more trials for a total of 13 trials.

So for 100 stories and two eggs a maximum of 18 drops.

Submitted by Steven on Sun, 02/07/2016 - 21:43

Try to keep the number of trials constant/fixed at any point.

Do this by decreasing by 1 the number of floors added at each stage. Drop from 15th floor. If eggs breaks will require at most 15 trials. If not then drop from 14 storeys higher, i.e. 29th floor. If egg breaks will still require at most 15 trials. Proceed similarly: Then 42nd floor. If egg breaks will have used at most 15 trials. Remaining floors to test, 54, 63, 73, 82, 90, 97 - at each of those the maximum number of trials is 15 still. At 97th floor we have done 9 trials and have 2 eggs remaining with only 3 more floors to test so we are good.

ajk44's picture

Submitted by ajk44 on Mon, 02/08/2016 - 11:05

Great work, Steven - I've hidden your answer under a button in case anyone wants to use your hint to work out a strategy for themselves before reading on.

Submitted by Steven on Sun, 02/07/2016 - 21:58

I had a small error in my calculations the first time which is how I ended up with 15. It can be done with 14 trials:

1st drop at 14. If necessary 13 more drops required for max 14 drops. 2nd drop at 27. Same idea. Remaining floors to test at include: 39, 50, 60, 69, 77, 84, 90, 95, 99. All will require at most 14 drops. At 99th floor test we have only 1 more floor to test and have used only 11 trials so still under 14. I haven't found a way to do it with 13.

ajk44's picture

Submitted by ajk44 on Mon, 02/08/2016 - 11:07

I wonder if 14 is the minimum... Can you prove it's impossible to guarantee you will find the answer in at most 13 drops?

Submitted by phoxa on Tue, 02/09/2016 - 14:20

18 is the max number I came to for the worst case.

You start by dividing the intervals by the square root of the number of floors left to test. So you test first the 10th floor, then you test the 19th floor (since sqrt(90) rounded down is 9), then the 28th (since sqrt(81) is 9 again), then 36th floor, etc.

Maybe rounding up gives the same max number, but I didn't try.
I didn't think of a proof to confirm that this is the best solution, although intuitively it seems so to me :)

Submitted by Anonymous on Thu, 05/11/2017 - 13:10

This is a good strategy, but what happens if the egg breaks on the first floor? Do you drop it from lower down?

Submitted by Aman Bansal on Mon, 05/15/2017 - 17:28

First things first, this solution is not for 2 eggs.
In the worst case, this solution would require 6 drops and 6 eggs.
So my solution is to first find the range of possible floors from where the egg would break. Then divide this range by 2 (round up or down depending on if the value is above or below the last tested floor) and test on that floor. So, you would always start with floor 50. An example of how this will work is given below.

(This in my opinion is one of the worst scenario)
Suppose the egg breaks when dropped from floor 1.
Steps :
1. So we start from floor 50, the egg breaks, so our new range is 1-50 and the half of that is 25.
2. We test at floor 25 and the egg breaks. Now, the range is 1-25 and the half of that is 12.5. As this is below 25, we round down to 12.
3. Now we test at floor 12 and the egg breaks again. New range 1-12 and half of that is 6.
4. Then we test at floor 6 and the egg breaks. New range 1-6 and half of that is 3.
5. We test at floor 3 and egg breaks again. New range 1-3 and half of that is 1.5 (rounded down to 1)
6. We test floor 1 and as the egg breaks, we know that the answer is floor zero (the ground floor).

This solution can be expanded to more floors which will require more eggs.

Submitted by matthew on Thu, 05/18/2017 - 13:20

That's an interesting Binary Search method that you've developed. What would happen if the sixth didn't break on floor 1? Would you need to test floor 2? What would happen if there were 200 floors? Clearly it would take more tests and probably more eggs, but how many more?

Can you find a strategy that wouldn't require as many eggs?