The Amazing Egg-Dropping puzzle

The Puzzle Description:

There is a building having ‘k’ floors and we have ‘n’ eggs. We have to determine the minimum number of attempts or trials to find the critical floor[the highest floor from which eggs survive]; in the worst case.

Assumptions:

1. All the eggs are identical.
2. If an egg doesn’t break from a floor, then it doesn’t break from any floors below it.
3. If an egg breaks from a floor, then it breaks if it is dropped from any floor above it.
4. An egg may break if dropped from the first floor.
5. An egg may not break even if dropped from the k-th floor.
6. The height of the floors is variable.

Discussion:

Let us think about a simpler version of the problem. That is if we have n=1 egg and k floors. Then how can we determine the critical floor?

If we observe we can’t go on dropping the egg from the topmost floor. Why? Suppose we have 10 floors and the critical floor is the 7th one. So if we start dropping from the 10th floor, the egg will break when dropped from the 10th floor. How will we know which is the critical floor; because there is no surety about from which floor below it eggs will not break; there is the only surety that the eggs will break from the floors above it. So the only way to start dropping is, from the first floor.

Then let’s see what is the best and worst case? The best-case occurs when the egg breaks when dropped from the first floor. So we can become sure that none of the floors is the critical floor. Here we know about the critical floor only in 1 attempt. And the worst-case occurs when the egg doesn’t break in any of the given floors. So to know about the critical floor we make k attempts, that is equal to the number of floors given. So the answer to the simple problem of n=1 egg and k floors is k. Because that is the maximum number of attempts required to determine the critical floor.

The problem becomes interesting if we have more than 1 egg. In this case, we have to determine the sequence of floors from which the eggs are to be thrown so that the worst-case is minimized; if we have n eggs and k floors.

Here the problem is to find the critical floor using the no. of eggs we have. It is like searching a number in a sorted array. Like we take the key(the number to be searched for) and compare; here we use the eggs. Think of the floor as a number, egg as the key, and dropping as the comparison. And why I compare it with a sorted array because if an egg doesn’t break from a floor it is guaranteed that it will not break from the floors below it. We can think the floors from which egg doesn’t break as 0 and from which the eggs don’t break as 1. So if we see from the ground, it will appear as 0, 0, 0,..,0,1,…,1 OR only 0’s OR only 1’s. So here we have to search for the 0 after which there are no 0’s.

So one might be tempted to use the binary search to find that 0. But here is the problem. We may have to make a fixed no. of comparisons. Why? Because we may or may not have log(n) eggs, which is required for the minimization. Also, we don’t know whether the chance of comparisons will be the same or reduce after a comparison is made i.e an egg is dropped, because if the egg breaks, our chance of making comparison decreases. It’s like we can make an infinite number of comparisons with the eggs but when the number of eggs is reduced to 1, then we have to make O(n) comparisons upward in order to determine the critical floor. Let’s see an example, where we have 2 eggs and 100 floors. So if we use binary search the answer will be ceil[log(n)], i.e is 7. In this process, we will first drop the egg from the 50th floor. If it doesn’t break we will go to the 75th floor and we can go on if the egg doesn’t break. But what will happen if the egg breaks on the 50th floor? Then we have to use the last egg and start dropping from the 1st floor and if the critical floor is the 49th floor, we have to keep dropping till that floor. And it is O(n). So clearly the binary search solution is not the best strategy for all the cases and will not result in the optimal solution.

So what we can do is to drop the eggs from each and every floor and consider the possibility of the egg breaking. From all the possibilities, we can take the minimum of the worst cases possible. Here worst case means the maximum number of droppings we have to make and making sure we know the critical floor in that case or path.

The above idea is conveyed by the following recursive equation.

This recursive solution can be optimized using the dynamic programming paradigm. So let’s understand what the equation is saying. At first, we drop an egg and that will add 1 to the answer. We don’t know whether the egg will break or not. So here we encounter 2 cases: first, the egg will break and we will have n-1 eggs, second, the egg will not break and we will have n eggs remaining. In the first case where the egg breaks, we don’t have to search above the floor, so the number of floors we have to search is reduced to x-1. In the second case where the egg doesn’t break, we have n eggs remaining and we don’t have to search the floors below it, so the number of floors we have to search for is reduced to k-x. And we can drop the 1st egg from all the floors, so x can be 1,2,…,k. Here as we can see after the first drop the problem is reduced to a combination of 2 sub-problems. This is the optimal substructure which increases the strength of our claim of using the above method to reach the optimal solution. However, it is not the validation through mathematical proof. In each case where x has a value, we take the maximum value because we are considering the worst case if we drop from that floor. And at last, we take the minimum of all those worst-case values.

After we find the answer i.e the optimal value, we may have several floors from which we can start our first dropping. So here is an instance of the minimal worst case if we have 100 floors and 2 eggs.

By using the DP solution we can find the answer as 14. In the above table, all the possibilities are shown. Like in the first case of the instance where the 1st egg breaks at 14 the floor, then we have to use the 2nd egg to find the critical floor in the worst case(13th floor is the worst case). And it shows if the 1st egg doesn’t break on the 14th floor, then which floor to choose so that the total no.of dropping don’t cross 14.

Note:

1. From the above discussion, the theory that if we have number of eggs equal to or greater than the ceil[log(n)] where n is the no.of floors given, then the answer is equal to ceil[log(n)]; seems to be true.
2. The above discussion is a sum of my observations and ways to understand the problem from scratch. So anybody is free to give constructive criticisms.
3. There are other approaches in existence, not discussed here.

Thank You for your patience!