Super Strong Eggs--- II
You are given just two eggs, and access to a 100-storey building. Both eggs are identical.
The aim is to find out the highest floor from which an egg will not break when dropped out of a window from that floor. If an egg is dropped and does not break, it is undamaged and can be dropped again. However, once an egg is broken, that’s it for that egg.
If an egg breaks when dropped from floor n, then it would also have broken from any floor above that. If an egg survives a fall, then it will survive any fall shorter than that.
Adopting best strategy what is the absolute minimum number of egg drops you need to reach the solution given any and every possible scenario?
Details and Assumptions :
- Issues related to terminal velocity, potential energy or wind resistance are immaterial.
You can solve Super Strong Eggs --I here .
You can solve Super strong eggs III here .
The answer is 14.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Let’s say we dropped our first egg from floor 50. If it broke, we’d be reduced to a one egg problem, so then we would have to start with our last egg from floor 1 and keep going up one floor at a time until that breaks. At worst, it will take us 50 drops.
If we started off with our first egg going up by floors ten at a time? We can start dropping our egg from floor 10; if it dont break, we try floor 20, then floor 30 … we carry on until the egg breaks and then we back off nine floors and step through these floors one at a time until we find a solution.
Worst case with this strategy? If we dropped eggs on every 10th floor all the way up, and our first egg broke on floor 100. This has taken us ten drops so far. Now we know the solution must lay somewhere between floor 91 and floor 99 and we have to go through these in ones, starting at floor 91. The worst case would be if the solution was on floor 99, and this would take us nine more drops to determine. The worst case therefore, if we go by tens, is 19 drops.
Problems where the answer lies lower down the building are taking less drops than when the answer lies higher up.
The way to reduce the worst case is to try to make all cases take the same number of drops.
If the answer lies somewhere in a floor low down, then we have extra space when we need to step by singles, but, as we get higher up the building, we’ve already used chances to get there, so there we have less drops left when we have to switch to going floor by floor.
Lets say we drop our first egg from floor n, if it breaks, we can step through the previous (n-1) floors one-by-one.
If it doesn’t break, rather than jumping up another n floors, instead we should step up just (n-1) floors (because we have one less drop available if we have to switch to floor by floor), so the next floor we should try is floor n + (n-1)
Similarly, if this drop does not break, we next need to jump up to floor n + (n-1) + (n-2), then floor n + (n-1) + (n-2) + (n-3) …
We keep reducing the step by one each time we jump up, until that step-up is just one floor, and get the following equation for a 100 floor building:
n + (n-1) + (n-2) + (n-3) + (n-4) + … + 1 >= 100
This summation is the formula for triangular numbers and can be simplified to:
n*(n+1)/2>= 100
This is a quadratic equation, with the positive root of 13.651. That is our absolute minimum number of egg drops --- Rounded up to 14.
Our first drop should be from floor 14, if egg survives we step up 13 floors to floor 27, then up 12 floors to 39.....
So the egg drops will be on floor 14 27 39 50 60 69 77 84 90 95 99 100.
The optimal strategy is to work our way through the floors outlined above until the first egg breaks, then back up to one floor higher than the previously tried floor and then proceed floor by floor until we find the exact solution.