How Strong is an Egg?

Question

You have two identical eggs. Standing in front of a 100 floor building, you wonder what is the maximum number of floors from which the egg can be dropped without breaking it. What is the minimum number of tries needed to find out the solution?

Answer 1

Now that you have got the answer by yourself, let me post what I was going to, as well. (A slow formal proof that $14$ is the minimum, and the answer for general $N$ in place of $100$.)

---

Just to be clear, the assumption in the problem is that all answers are possible, from $0$ to $100$ inclusive: it is possible the egg breaks when dropped from the very first floor itself, it is possible the egg can survive a fall from even the $100$th floor, and everything in between. (Also, the result of a fall is either that the egg breaks, and can no longer be used, or that it doesn't break and the fall has no effect on it whatsoever.)

Let us first solve the problem where you have only one egg. Then it should be clear that the only solution is to drop it from the first floor, then if it doesn't break drop it from the second floor, and so on up to $100$ floors. [Proof: Suppose you first drop the egg from a height $h_1$, then if it doesn't break you drop it from a height $h_2$, and so on. Then,

• $h_1$ must be $1$. Because if $h_1 > 1$, and it breaks when you drop it from height $h_1$, then you have the egg no more, and have no way of distinguishing between the potential answers $0, \dots, h_1-1$.
• $h_2$ must be $h_1 + 1$, and in general $h_{n+1} = h_n + 1$, for a similar reason: if the egg breaks when you drop it from $h_{n+1} > h_{n} + 1$, then you have no way of distinguishing between the potential answers $h_{n}, \dots, h_{n+1}-1$. So $h_1, h_2, h_3, \dots$ are $1, 2, 3, \dots$ respectively. $\Box$]

So now with two eggs, suppose you drop it from a height $h_1$, then if it doesn't break you drop it from a height $h_2$, and so on. (Obviously to be optimal this will be an increasing sequence, since if the egg doesn't break when dropped from some height, it is never necessary to drop it from a smaller height as you already know the result.) For convenience, denote $h_0 = 0$. If on some drop $h_{n+1}$ the egg breaks ($n \ge 0$), then you are left with the task of distinguishing between the possible answers $h_n, \dots, h_{n+1}-1$ with just one egg, which by the reasoning of the first part above, takes (up to) $h_{n+1} - h_{n} - 1$ drops (basically you drop the egg from $h_{n} + 1$, then from $h_{n} + 2$, and so on up to $h_{n+1} -1$). So the total number of drops needed in this scenario is $n+1$ (for the drops $h_1$ to $h_{n+1}$) followed by $h_{n+1} - h_{n} - 1$ drops, for a total of $ n + 1 + h_{n+1} - h_{n} - 1$, namely $n + h_{n+1} - h_{n}$ drops (where $n\ge 0$). In the worst case, we will incur the maximum cost of this over all $n$, and that is what we want to minimize: we want to minimize $$\begin{align}\max( &0 + h_1,\\ &1 + h_2 - h_1, \\ &2 + h_3 - h_2, \\ &\dots,\\ &n + h_{n+1} - h_{n})\end{align}$$ where $n$ now is such that $h_{n+1} = 100$ (if your egg never breaks, you'll keep using the first egg until you drop it from the $100$th floor, so we can wlog assume that the $h_i$s form a finite sequence ending with $100$). Note that the sum of all these quantities telescopes, and it is $\frac{n(n+1)}{2} + 100$. So since the sum of $n+1$ numbers is that much, the largest of them is at least $\frac{1}{n+1}$th of it, namely $$\frac{1}{n+1}\left(\frac{n(n+1)}{2} + 100\right) = \frac{n}{2} + \frac{100}{n+1} \ge 10\sqrt{2} - \frac12 \approx 13.6,$$ so we need at least $14$ drops.

And the method for actually achieving $14$ drops suggests itself: to make the maximum equal when the sum is fixed, the general way is to make all of them as equal as possible, which suggests we can take $h_1 = 14$, then $h_2 - h_1 = 13$ (so $h_2 = 14 + 13 = 27$), then $h_3 = 14 + 13 + 12$, and so on up to $h_{11} = 14 + 13 + \dots + 4 = 99$, and then $h_{12} = 100$.

(There are many other solutions, e.g. $h_1 = 7$, then $h_2 = 7 + 13$, $h_3 = 7 + 13 + 12$ and so on up to $h_{14} = 7 + (13 + 12 + \dots + 2 + 1) = 100$, but the salient fact is that $13 + 12 + \dots + 2 + 1 = 91 < 100$, while $14 + 13 + \dots + 2 + 1 = 105 > 100$. If instead of $100$ we were given $105$, the answer would still be $14$, and the method would be unique.)

Of course, we did not here use any special property of $100$, and repeating the above argument for general $N$ shows that the number of steps needed is: $$ \left\lceil \sqrt{2N} - \frac{1}{2} \right\rceil$$

A simpler alternative way of saying this is: $$\text{the smallest number $n$ such that $\frac{n(n+1)}{2} \ge N$.}$$

Answer 2

I found the solution. Here it is:

The easiest way to do this would be to start from the first floor and drop the egg. If it doesn’t break, move on to the next floor. If it does break, then we know the maximum floor the egg will survive is 0. If we continue this process, we will easily find out the maximum floors the egg will survive with just one egg. So the maximum number of tries is 100 that is when the egg survives even at the 100th floor.

Can we do better? Of course we can. Let’s start at the second floor. If the egg breaks, then we can use the second egg to go back to the first floor and try again. If it does not break, then we can go ahead and try on the 4th floor (in multiples of 2). If it ever breaks, say at floor x, then we know it survived floor x-2. That leaves us with just floor x-1 to try with the second egg. So what is the maximum number of tries possible? It occurs when the egg survives 98 or 99 floors. It will take 50 tries to reach floor 100 and one more egg to try on the 99th floor so the total is 51 tries. Wow, that is almost half of what we had last time.

Can we do even better? Yes we can. What if we try at intervals of 3? Applying the same logic as the previous case, we need a max of 35 tries to find out the information (33 tries to reach 99th floor and 2 more on 97th and 98th floor).

Interval – Maximum tries

    1  – 100
    2  – 51
    3  – 35
    4  – 29
    5  – 25
    6  – 21
    7  – 20
    8  – 19
    9  – 19
    10 – 19
    11 – 19
    12 – 19
    13 – 19
    14 – 20
    15 – 20
    16 – 21

So picking any one of the intervals with 19 maximum tries would be fine.

Instead of taking equal intervals, we can increase the number of floors by one less than the previous increment. For example, let’s first try at floor 14. If it breaks, then we need 13 more tries to find the solution. If it doesn’t break, then we should try floor 27 (14 + 13). If it breaks, we need 12 more tries to find the solution. So the initial 2 tries plus the additional 12 tries would still be 14 tries in total. If it doesn’t break, we can try 39 (27 + 12) and so on. Using 14 as the initial floor, we can reach up to floor 105 (14 + 13 + 12 + … + 1) before we need more than 14 tries. Since we only need to cover 100 floors, 14 tries is sufficient to find the solution.

Therefore, 14 is the least number of tries to find out the solution.

Answer 3

The critical strip of eggs is the interval $C:=[k,k+1]$ such that, when an egg is dropped from a height $\leq k$ it survives, and when it is dropped from a height $\geq k+1$ it brakes.

The numbers $$h_r(n)\qquad(r\geq0,\ n\geq0)$$ ("allowed length for $r$ eggs and $n$ trials") are defined as follows: If we know that $C$ lies in a certain interval of length $\ell\leq h_r(n)$ we can locate $C$ with $r$ eggs in $n$ trials, but if we know only that $C$ lies in a certain interval of length $\ell>h_r(n)$ then there is no deterministic algorithm that allows to locate $C$ with $r$ eggs in $n$ trials for sure. Obviously $$h_0(n)=1\quad(n\geq0)\ ,\qquad h_r(0)=1\quad(r\geq0)\ .$$ The numbers $h_r(n)$ satisfy the recursion $$h_r(n)=h_{r-1}(n-1)+h_r(n-1)\qquad(r\geq1,\ n\geq1)\ .\qquad(*)$$ Proof. Assume $C$ lies in a certain interval $I$ of length $\ell:=h_{r-1}(n-1)+h_r(n-1)$. We may as well assume that the lower end of $I$ is at level zero. Drop the first egg at height $h_{r-1}(n-1)$. If it brakes then $C$ is contained in the interval $[0,h_{r-1}(n-1)]$ and can be located with the remaining $r-1$ eggs in $n-1$ trials. If it survives then $C$ is contained in the interval $[h_{r-1}(n-1),\ell]$ of length $h_r(n-1)$ and can be located with the $r$ eggs in $n-1$ trials. This proves $h_r(n)\geq\ell$.

Conversely, assume that we know only that $C$ lies in a certain interval of length $\ell'>\ell$ and that there is an algorithm that locates $C$ with $r$ eggs in $n$ trials. This algorithm would tell us the height $k$ at which we should drop the first egg. If $k>h_{r-1}(n-1)$ and the egg brakes or if $k\leq h_{r-1}(n-1)$ and the egg survives it would be impossible to finish the task, as the remaining interval that contains $C$ is larger than allowed for the remaining resources. It follows that $h_r(n)\leq\ell$.

From $(*)$ we obtain $$h_1(n)=n+1\ ,\quad h_2(n)={1\over2}(n^2+n+2),\quad h_3(n)={1\over6}(n^3+5n+6)\qquad(n\geq0)\ .$$ As $h_2(13)<100<h_2(14)$ we need at least $14$ trials to locate $C$ (or eliminate $C\subset[0,100]$) in the original setup.