Problem: We are doing an experiment to find the highest floor of a building that we can drop an egg without breaking it. If there are 100 floors and we have only 2 eggs what is the minimum number of egg drops we need to make to be able to definitively identify the lowest egg-breaking floor.
Before going into a solution it's wise to state our assumptions:
- Both eggs have identical strength properties.
- An egg that survives a drop has the same strength properties as an egg that hasn't ever been dropped.
- If an egg dropped from floor X breaks then it would also break when dropped from all floors above X.
- If an egg dropped from floor X does not break then it would not break when dropped from all floors below X.
First, let's consider some variants of this problem to get a better understanding of the problem space.
If we had an unlimited supply of eggs our best strategy would be to employ a binary search as this puzzle is effectively a search for an item in a sorted collection and binary search is asymptotically optimal in this case. So you would go to the 50-th floor and drop an egg. If if breaks go to the 25-th floor. If it doesn't break go to the 75-th floor, etc. At each drop you are halving the number of possible floors that could be the egg-breaking threshold so, as to be expected of many divide-and-conquer approaches, it has a logarithmic expected number of drops before you find the egg-breaking threshold.
If we have only 1 egg available the "cannot re-use a broken egg" constraint forces us to abandon the binary search approach and go with a linear search whereby we start dropping at the first floor and go up one floor at a time until we break the egg. This is the only solution we can employ that definitely tells us which floor is the egg-breaking floor. To determine the worst case analysis for this strategy we need to consider the case that the egg-breaking floor is the top floor. Clearly, for an n-storey building which has n floors, the worst case drop count is n.
But what about the case when we have 2 eggs to play with? Firstly, let's assume that there is an optimal solution and define some terminology.
Let T = the unknown egg-breaking floor. This is an (unknown) constant.
Let n = the no. of floors left to test. Initially = 100.
Let d* = the minimum number of drops required to identify T with absolute certainty with 2 eggs. This is our assumed optimal solution. Clearly, d* <= 100.
Let P(n,d) = the problem of finding T amongst n consecutive floors with d drops using at most 2 eggs.
The initial problem is clearly P(100,d*). So the only course of action available to us on "iteration 1" is to drop an egg at some floor, x1, where 1 <= x1 <=100. The only possible outcome is that it breaks or it doesn't break. If it breaks we must proceed to the linear search technique with the second egg starting at the lowest untested floor. In the worst case we will need another x1-1 drops to determine T definitely giving a total of x1 drops. Since we defined d* to be the minimum number of drops needed then it follows that x1 = d*.
If the egg doesn't break T is still unknown and we still have 2 eggs. The only difference is that we now have fewer floors to test and 1 less drop to use, so the problem is now equivalent to P(100-x1,d*-1). Again, the only course of action available to us on "iteration 2" is to drop an egg at some floor, x2, where 100-x1 < x2 <= 100. If the egg were to break on floor x2 we would resort to the linear search with the second egg and thus incur x2 drops in the worst case. Since we know we have at most d*-1 drops left this implies: x2 <= d*-1. So substituting in for d* we have: x2 <= x1-1.
Thus a recursive pattern is observed: on iteration i we drop an egg at the floor x-(i-1) above the lowest untested/unknown floor. We do not know the value of T so we do not know where we are going to get egg breaks, but this strategy ensures that when a break happens we do not incur fewer than d* total drops because that would violate our optimal solution definition.
The recursive pattern mentioned above can also help us identify d*, which is what was asked of us! To see this consider the case when successive egg drops result in "no break" outcomes. The pattern specifies that we need to step up a monotonically-decreasing number of floors: x, x-1, x-2, x-3, x-4, ...,1. So in the worst case when T is the top floor, since n=100 we note that:
The left hand side is the sum of an arithmetic progression which reduces to:
The maximum value of x that we can substitute into this such that this inequality still holds is x = 13 point something but x must be an integer since it is not possible to advance a fractional number of floors, so we settle on x=14=d*. Thus the least possible drops required to definitively find T when n=100 is 14.
17 Nov 2008 Damien Wintour