Egg Dropping Puzzle

There is a building with 100 floors. There are two identical eggs. When we drop an egg from any floor of the building, it will either break or survive. If an egg drop survives, it will survive the drop from lesser floors. If an egg drop breaks, it will break from higher floors as well.

We need to find the strategy which can take the minimum number of drops to find the threshold floor from which an egg drop can survive. What is the maximum number of drops required in the worst case?

Assumptions: These are strong eggs because they can be dropped multiple times without breaking as long as they are dropped from floors below their “threshold” floor, floor N. But once an egg is dropped from a floor above its threshold floor, it will break. Find the minimum number of drops required to figure out N.

Solution Idea

Let's assume in the worst scenario, n number of drops are required to find the threshold floor in a 100 storey building.

Instead of 2 eggs, if we have only one egg, we have only one choice to do a linear search for finding the threshold floor: we can try from the first floor and keep moving to the next floor until that egg breaks. In this case, the worst number of drops will be 100.

But here we are provided with two eggs and our idea to minimize the number of drops. So another approach that comes to mind is to use a binary search approach:

Divide the floors into half for each egg i.e. follow the binary path we drop the first egg from the 50th floor. If it doesn’t break, try the middle floor of the other half.
Or in the worst case if it breaks then we need to check each floor below of 50th floor starting from the 1st floor that gives us the worst number of drops as 50.

But now the critical question is: can we optimize the number of drops? Are there some insights into the problem which help us to do it efficiently? The choice of the floor for the first drop of the egg is important. This choice must be optimal so that it gives us the minimum number of drops. How do we find such an optimal floor for the first drop? Let's think!

Suppose we first try dropping from xth floor. If it breaks then in the worst case: we need x-1 drop with 2nd egg. If the first egg doesn't break then in the next attempt: we can try it from the (x + (x-1))th floor because if it breaks then we need to check x-2 floors with the 2nd egg.

Similar way if it doesn't break then we can try from the x+ (x-1) + (x-2) floor and then x + (x-1) + (x-2) + (x-3) and so on. Here last floor is 100. So sum of this series should 100.

=> x + (x-1) + (x-2) + (x-3) + ...+ 1 = 100

=> x(x + 1)/2 = 100

=> x = 13.6 ~ 14 (rounding up to next integer we get x=14)

Hence we have minimized the floor number to 14th floor if it breaks at 14th floor we need to check the remaining 13 from the bottom ,if it doesn’t then check on 14+13 = 27th floor, if breaks here then check out the floors 15 to 26 ,else check on 27+12 = 39th floor and follow the same pattern as followed above.