Highest Floor to Drop Egg Without Breaking

You have two identical eggs. What is the highest floor of a 36-story building from which you can drop an egg without it breaking? If an egg survives a drop without breaking, it is as good as new. That is, you can then conduct another dropping experiment with it. What is the smallest number of drops that is sure to determine the answer?

Answer:

Take the first egg, and drop it from 6, 12, 18, 24, 30, 36. Let's suppose, if it breaks on 18th floor, take the second egg and drop it from 13th floor till 17th floor. With that, you will come to know the highest floor from which you can drop without breaking.

Generic Solution

If the building has n floors, then take the first egg and drop it from sqrt(n), 2*sqrt(n), 3*sqrt(n) and so on. If it breaks on any floor, take the second egg and start dropping from the next floor to the previous floor where we tried.

The maximum no.of times we drop in this method is 2*sqrt(n).

Even More Generic Solution

If the building has n floors, and if we have m eggs, then take the first egg, and drop it from 1*n^((m-1)/m), 2*n^((m-1)/m), .. , n^(1/m)*n^((m-1)/m).

If it breaks on any floor, and let's say floor x is the previous floor from where it has not been broken, then start dropping the egg from x + 1*n^((m-2)/m), x + 2*n^((m-2)/m), ... x + n^(1/m)*n^((m-2)/m) and so on.

The maximum no.of times we drop in this method is m*n^(1/m).

Explanation:

If there is only one egg, then one has to go linearly one by one from the first floor.

If there are two eggs, then to utilize both the eggs efficiently, first egg should find set of floors, which contains our floor, and second egg should find our floor exactly. If we take square root of the no.of floors, then this will give the optimum value. If there are 100 floors, then the first egg is going to find 10 floors which contains our final floor, by dropping from 10, 20, .. and so on. Once first egg is broken, second egg is used to find in the remaining.

If there are m eggs, then dropping egg n^(1/m) times in each iteration would give the best result. In the first iteration, if we have to drop the egg n^(1/m) times, we have to split the floors by n^((m-1)/m). So, the floors that we try would be, 1*n^((m-1)/m), 2*n^((m-1)/m), ... and so on.

Once the egg is broken in a floor, we have to take that floor and the previous floor where we tried, as the floors that we have, and one less egg than the previous.

now, we have m-1 eggs, and the total no.of floors is n^(m-1)/m (since in the previous iteration, the floors that we used are n^((m-1)/m) floors apart.)

If we apply the same formula as before, the floors would be (n^((m-1)/m))^((m-2)/(m-1)) apart.

n^((m-1)/m) is the no.of floors.
Previously, we used (m-1)/m as the power, when there are m eggs. Now, there are m-1 eggs. So, the power is (m-2)/(m-1).

If we simplify that, it would become n^((m-2)/m). We will use the egg n^(1/m) times in this iteration also. So, the floors would be x + 1*n^((m-2)/m), x + 2*n^((m-2)/m), ... x + n^(1/m)*n^((m-2)/m)