扔鸡蛋问题

Problem

You have two eggs, and you're in a $100$ story building. You want to determine with certainty the lowest floor from which you can drop an egg without it breaking. You can perform the following egg drop experiment: go to a floor, drop an egg, and see if it breaks. If it doesn't break, you can re-use that egg for future experiments. What's the minimum number of egg drops ($N$) you need to determine this floor? Note: that means no matter what floor it is, your algorithm must be able to compute it in $\le N$ steps.

Think about the problem for a little while; when you think you have an answer, click on the button below!

Discussion

If the problem were just one egg, the only thing you could do is drop it from floor $1$, then floor $2$, all the way till floor $100$. Thus the minimum is $100$ egg drops in this strategy.

If the problem were many many eggs (for example $100$), then we could use binary search, i.e., drop one egg at floor $50$, if it breaks drop another egg at floor $25$ else drop an egg at floor $75$. The minimum would be $7$ egg drops in this strategy.

But alas, we only have two eggs. One idea inspired by binary search is drop the first egg at floor $50$, then use the second egg to go through the rest of the floors. The minimum would be $51$ egg drops in this strategy.

But, we want to use our resources as efficiently as possible. In the above strategy, what if our egg survives? Then we could drop it $75$ and then the minimum would be $50$ ($50$ egg drops if it does break, $27$ if it doesn't).

In fact, our strategy is going to be taking one egg and dropping it at some increasing sequence of floors till it breaks, then if it breaks go sequentially through the remaining floors with the second egg. For example, drop the first egg from floors $10$, $20$, $30$, ..., $100$ until it breaks (if it doesn't break, then we solved it in $10$ drops). Let's say it breaks on floor $30$. Then we have to test the second egg from floors $21$, $22$, ..., until at most floor $29$. The worst case performance in this strategy is if the actual floor is $99$, which means we test egg one $10$ times and then egg two $9$ times, so $19$.

Perhaps we can be more efficient about this strategy. It seems that the reason it performs poorly is because for the second egg, we will always have to test $9$ cases in the worst case. Thus this algorithm is particularly better when the floor is actually on a lower floor. What if there was some way to make each case occur with an approximately equal number of egg drops?

Let's say we initially drop egg one from floor $x$. Then at worst case, we will have $x-1$ egg drops from the second egg, so $1+(x-1)=x$ drops in total. If egg one survives from floor $x$, we want to drop it from floor $y$. We will have to test from $x+1$ to $y-1$ ($y-x-1$ drops) for $y-x+1$ drops in total. In order to make all the cases approximately equal, we want $x=y-x+1\implies y=2x-1$. In fact, this floor number is intuitive, as we need to account for the one egg drop that we already performed by reducing the number of drops for the second egg by one, which means we want to go up not $x$ floors, but $x-1$ floors. For the third choice in floors, we will have already made two drops, so we need to go up $x-2$. Thus the strategy is to drop it at floors $x$, $x+(x-1)$, $x+(x-1)+(x-2)$, ...; with this strategy, each case will always use exactly $x$ egg drops. Finally, since we want to stop dropping eggs one once we get to the $100$th floor, we want the last drop to be $\ge100$. Hence $$x+(x-1)+(x-2)+\dots+1=\frac{x(x+1)}2\ge100\implies x\ge14.$$ So this strategy gives $14$ drops.

In general, for $n$ floors, this method solves the problem in $O(\sqrt n)$. Fun fact: even the above strategy of dropping egg one at floors $10$, $20$, ... gives $O(\sqrt n)$. However, this algorithm gives an absolute minimum number of drops.

Information Theory

It's very hard to prove that this algorithm gives the absolute minimum number of steps. Most information theory proofs involve formalizing the concept of a strategy and showing that for any other strategy, there is some case where it does at least as bad as your strategy. I'll conclude with the way I would prove this optimality (and I'd like to see people post if they have better ways to prove this).

Proof. Let $S$ be an optimal strategy to solve this problem. In particular, $S$ takes two eggs, chooses one arbitrarily to be egg one ($E_1$) and the other to be egg two ($E_2$), then assigns a sequence of drops for $E_1$ and $E_2$. Since the eggs both function equally and are indistinguishable, we can transform $S$ into a strategy where we perform a sequence of drops on $E_1$ until it breaks, then on $E_2$.

Let's say $S$ drops $E_1$ from floors $a_1,a_2,\dots,a_m$, stopping when it breaks. We can assume $a_1<a_2<\dots$ since no new information is gained by dropping it from a floor less than one we've already seen. Let $a_0$ be floor $0$ for notational ease. Suppose $E_1$ breaks on floor $a_k$. Then we will necessarily have to test floors $a_{k-1}+1,\dots,a_k-1$, since it is possible that the target floor is any of these floors. Therefore, in total we will need $a_k-a_{k-1}-1$ drops for $E_2$ and $k$ drops for $E_1$, a total of $(k-1)+a_k-a_{k-1}$.

Let $\Delta_k=a_k-a_{k-1}$. Now we have to take the worst case of all of these, i.e., we need to compute

$$\max\left\{\Delta_1,1+\Delta_2,2+\Delta_3,\dots\right\}$$

where $\Delta_i>0$ for all $i\ge1$ and $\Delta_1+\Delta_2+\dots=n$ ($n=100$ in this case). Note: we deduced that sum from the fact that $a_k=n$ is necessarily true. Finally, by the averaging principle, we must have

$$\begin{align*} \max\{\Delta_1,1+\Delta_2,2+\Delta_3,\dots\}&\ge \frac{\Delta_1+(1+\Delta_2)+\dots+(m-1+\Delta_m)}m\\&= \frac{(1+2+\dots+m-1)+(\Delta_1+\Delta_2+\dots+\Delta_m)}m\\&= \frac{m-1}2+\frac{n}m.& \end{align*}$$

By AM-GM, we have

$$\frac{m-1}2+\frac{n}m=-\frac12+\left(\frac{m}2+\frac{n}m\right)\ge-\frac12+2\sqrt{\frac{n}2}$$

so any strategy will take at least that many steps. When $n=100$, that means any strategy needs $-\frac12+2\sqrt{100/2}\approx13.6$ egg drops, so the minimum is $\lceil13.6\rceil=14$. It thus suffices to check that $14$ is achievable, but we have already done this in the previous section, so we are done. $\blacksquare$