Egg Drop Puzzle

by Created: 26 Apr 2014 Updated: 26 Apr 2014

Given an N-story building and M eggs, how would you find out the highest floor of the building from which you can drop the eggs before they break? Eggs may be dropped again until broken.

The original problem was stated like this:

Given a 100-story building and only two eggs, how would you find out the highest floor of the building from which you can drop the eggs before they break?

which corresponds to the case that N=100 and M=2.

SPOILER BELOW

The algorithm given in the comments is: Try dropping the first egg from floors \(F_i = 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100\ (1 \le i \le 12)\) in that order.1 If it never breaks, then the answer is 100. If it breaks on some floor \(F_i\), then drop the second egg from the floor immediately above the last known good floor (<\(F_{i-1} + 1\), with \(F_0 = 0\)) and continue incrementing the floor by 1 until the egg breaks. The last floor before the second egg breaks is the answer. The worst-case number of trials required is then 14, corresponding to the case that the first egg broke on floor 14 and the second egg broke on floor 13, for a total of 14 trials.

I will show that this algorithm is correct for \((M,N) = (2,100)\), and generalize it to any number of floors and eggs.

We need one node in the search tree per floor. If we have at least \(M > log_2(N)\) eggs, then this problem reduces to binary search, and the worst-case requires \(\lfloor\log_2(N)\rfloor + 1\) trials. If we have \(M=1\) eggs, then this problem reduces to linear search, and worst-case requires \(N\) trials.

For other values of M, the search space is in-between linear and binary, a kind of truncated binary tree in which we are allowed to follow one direction (breaks) at most M-1 times, because after M-1 breaks, we must always take only the other direction (doesn’t break) until it finally breaks that one last time. This is equivalent to counting the number of binary strings of length T containing at most M zeroes. Then the answer to our question is the minimum T such that this count is \(\ge N\).

The number of binary strings of length T containing exactly k zeros is \({T \choose k}\). So, the number of binary strings of length T containing at most M zeros is \(\sum_{k=0}^{M} {T \choose k}\). This is OEIS sequence A08949 and has no closed-form solution for general M.

For M=2, we can solve it exactly:

\begin{align} {T \choose 0} + {T \choose 1} + {T \choose 2} &\ge N\\ 1 + T + \frac{T(T-1)}{2} &\ge N\\ T^2 + T + 2(1-N) &\ge 0\\ (T + \frac{1}{2})^2 - \frac{1}{4} + 2(1-N) &\ge 0\\ T &\ge -\frac{1}{2} \pm \sqrt{\frac{1}{4} - 2(1-N)}\\ T &= \lceil \frac{-1 + \sqrt{8N - 7}}{2}\rceil\\ \end{align}

For N=100, this yields the expected answer, T=14.

For other M, because we’re using small values of M and N, we could simply brute-force it:

from scipy.misc import comb
from math import log
def trials(N, M):
    """Given an N-story building and M eggs,
    calculate the smallest number of trials required
    to find the highest floor of the building from
    which eggs can be dropped without breaking."""
    T = int(log(N, 2))
    while (True):
        total = sum(comb(T, k) for k in xrange(0,M+1))
        if (total >= N):
            return T
        T += 1
print trials(100,2)
=> 14

Here’s a chart of how the number of trials varies with M:

fig,ax = plt.subplots(1,1)
N = 1000
X = xrange(2,10)
Y = [trials(N,m) for m in X]
ax.plot(X, Y)
ax.set_xticks(X)
ax.set_ylim([0,int(1.5*sqrt(N))])
ax.set_xlabel('M')
ax.set_ylabel('Trials')
ax.set_title('Trials needed for {0} floors and M eggs'.format(N))
fig.show()

note/eggdrop.png

  1. Notice that the differences between floors for the first egg decrease by 1 until reaching 1 (27-14=13, 39-27=12, … 100-99=1). This is due to the Pascal’s triangle/binomial coefficients inherent in the search tree. ↩