Two Eggs and One Hundred Floors, math that surprises you lesson

A building has 100 floors, and somewhere there may be a lowest floor from which a dropped egg breaks, or perhaps no floor breaks it at all. You have two test eggs, and a broken egg is gone for good. How can you find that floor with certainty using as few drops as possible? This page shows why halving the building fails with two eggs, builds a plan that never needs more than 14 drops, and uses triangular numbers to prove that 13 drops are not enough.

Key terms

Egg drop problem

Definition The egg drop problem, in its classic form, is an idealized puzzle about a building with floors numbered 1 to 100. There is an unknown threshold floor. An egg dropped from the threshold or any floor above it breaks, and an egg dropped from any floor below it survives undamaged and can be dropped again. The threshold may be any of the floors 1 to 100, or no floor of the building may break an egg, so there are 101 possible answers. You have two identical eggs, and a broken egg cannot be used again. Each drop is made from one floor and shows only whether the egg breaks, and the choice of the next floor may depend on every result so far. The task is to find a strategy that always identifies the answer and needs as few drops as possible in the worst case. The answer is 14 drops. Drop the first egg from floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99 and 100 in turn until it breaks. Then drop the second egg, from the bottom up, from each floor between the highest floor where the first egg survived (the ground, if there is none) and the floor where it broke, until the second egg breaks. The lowest floor where an egg broke is the threshold, and if the first egg survives even at floor 100, no floor breaks an egg. No strategy can guarantee the answer within 13 drops. The eggs are a mathematical model with perfectly predictable behavior, not a claim about real eggs.

In plain words The first egg takes big steps up the building, each step one floor shorter than the one before, until the roof cuts the last step short. Every drop of the first egg uses up part of the budget, so the steps shrink to make sure that whenever the first egg breaks, the second egg can check the floors in the last step one by one and still finish within 14 drops.

Example Suppose the threshold is floor 73. The first egg survives at 14, 27, 39, 50, 60 and 69 and breaks at 77 on the seventh drop. The second egg survives at 70, 71 and 72 and breaks at 73, so the answer is found in 11 drops. Suppose instead the threshold is floor 26. The first egg survives at 14 and breaks at 27, and the second egg survives at every floor from 15 to 25 and breaks at 26. That is 2 drops of the first egg and 12 of the second, 14 in all. At the bottom of the building, if the threshold is floor 1, the first egg breaks at 14 and the second breaks at 1, so two drops settle it. At the top, the steps 14, 13, 12 and so on down to 4 reach floor 99 after 11 drops, and the twelfth drop is from floor 100 instead of from a floor above the roof. A break there means the threshold is floor 100, and survival means no floor breaks an egg.

Worst-case analysis

Definition Worst-case analysis judges a strategy by the largest cost it can need over every input the problem allows. In the egg drop problem the inputs are the 101 possible answers and the cost is the number of drops. A strategy guarantees a result within $d$ drops when no possible answer makes it use more than $d$ drops. The best worst case of a problem is the smallest worst-case cost among all strategies that always find the right answer. Showing that a number is the best worst case takes two parts, a strategy that achieves it and an argument that no strategy does better.

In plain words Imagine that the threshold is chosen by someone who knows your plan and wants you to work as hard as possible. A plan that is quick for most thresholds but slow for one of them is judged by that one.

Example With the plan above, the threshold at floor 1 takes 2 drops, the threshold at floor 73 takes 11, the threshold at floor 100 and the case with no breaking floor take 12 each, and the threshold at floor 26 takes 14. Checking all 101 possible answers shows that 22 of them take exactly 14 drops and none takes more, so the worst case of the plan is 14 drops. The plan does not promise that every case takes 14 drops, only that none takes more. The puzzle gives no probabilities for the thresholds, so an average number of drops is not part of the question.

Binary search

Definition Binary search finds an unknown value among possibilities that lie in order. Each test splits the remaining possibilities as evenly as possible, and the search keeps only the part that agrees with the result. In the egg drop problem a drop from floor $x$ shows whether the threshold is at most $x$ , when the egg breaks, or above $x$ , when it survives. Each test has two results, so $d$ tests can tell apart at most $2^d$ possibilities, and binary search finds the value within $d$ tests whenever there are at most $2^d$ possibilities.

In plain words Ask the question that cuts the remaining possibilities in half. Each answer leaves about half of them, so a long list shrinks to one value after a few tests. The catch in this puzzle is that every break uses up an egg.

Example With at least seven eggs, so that every drop can afford a break, binary search finds the threshold among the 101 possible answers in at most 7 drops. The number of possible answers left falls to at most 51, 26, 13, 7, 4, 2 and finally 1. No method does it in 6 drops, because 6 drops have only $2^6 = 64$ possible patterns of results, fewer than 101. With two eggs, halving stops working after the first break. If the first egg breaks at floor 50, the threshold is one of the floors 1 to 50 and only one egg is left. That egg has to be dropped each time from the lowest floor not yet known to be safe, because a break from any higher floor would leave at least two possible answers and no egg to tell them apart. The thresholds 49 and 50 then take 1 drop at floor 50 and 49 more, which is 50 drops.

Triangular numbers

Definition For each whole number $d \ge 1$ , the triangular number $T_d$ is

T_d = 1 + 2 + \cdots + d,

the number of dots in a triangle with rows of $1, 2, \dots, d$ dots. The first few are 1, 3, 6, 10 and 15, and we set $T_0 = 0$ . Two copies of the triangle fit together into a rectangle of $d$ rows with $d + 1$ dots each, so

T_d = \frac{d(d + 1)}{2}.

In the egg drop problem with two eggs and $d$ drops, the largest number of floors for which the threshold can always be found is $T_d$ , which means $T_d + 1$ possible answers including the case of no breaking floor.

In plain words With two eggs and $d$ drops, the first step up the building can be $d$ floors, the next $d - 1$ floors, and so on down to $1$ . Adding the steps gives a triangular number, the tallest building the eggs can handle.

Example One egg with $k$ drops can handle at most $k$ floors, because it has to go up one floor at a time. With two eggs and $d$ drops, the first drop can be at most $d$ floors above the ground, since a break leaves the floors below it to one egg with $d - 1$ drops. If the egg survives, the floors above it form a smaller building to be searched with two eggs and $d - 1$ drops. Repeating the argument, two eggs and $d$ drops handle at most $d + (d - 1) + \cdots + 1 = T_d$ floors, and a plan with exactly these steps handles that many. For 100 floors,

\begin{gathered} T_{13} = \frac{13 \cdot 14}{2} = 91, \\[0.4em] T_{14} = \frac{14 \cdot 15}{2} = 105, \end{gathered}

so 13 drops cannot cover 100 floors and 14 drops can. The full 14-drop plan would reach floor 105, and in a building of 100 floors its last step is cut short at the roof.

Check yourself

A building has 36 floors, and you have two eggs. What is the fewest number of drops that always finds the threshold, and from which floors should the first egg be dropped?

Show the answer

The triangular numbers give $T_7 = 28$ and $T_8 = 36$ , so 7 drops handle at most 28 floors and 8 drops handle exactly 36. The fewest is 8 drops. Use steps of 8, 7, 6, 5, 4, 3, 2 and 1 floors, so the first egg is dropped from floors

8, 15, 21, 26, 30, 33, 35, 36.

If the first egg breaks on its $k$ th drop, that step was $9 - k$ floors, so $8 - k$ untested floors lie below the break, and the second egg needs at most $8 - k$ more drops. That makes at most 8 drops in every case. If the first egg survives at floor 36, no floor breaks an egg, which is also found in 8 drops.

A friend suggests dropping the first egg every 10 floors, at 10, 20, 30 and so on up to 100, and then checking the floors below the break one at a time. What is the worst case of this plan, and why does it lose to the 14-drop plan?

Show the answer

If the first egg breaks at floor $10k$ on its $k$ th drop, the second egg checks the 9 floors below it, from $10k - 9$ to $10k - 1$ , which can take 9 more drops. The worst case is a break at floor 100 on the tenth drop followed by 9 drops at floors 91 to 99, which happens when the threshold is floor 99 or floor 100. That is 19 drops, five more than the 14-drop plan. Equal steps make late breaks expensive. Every survival of the first egg costs one drop, but the gap the second egg must search stays 9 floors, so the total grows as the first egg climbs. Shrinking each step by one floor makes up for the drop that the first egg has already used.

Extend the puzzle to three eggs and 100 floors. What is the fewest number of drops now?

Show the answer

Let $G(d)$ be the largest number of floors that three eggs and $d$ drops can handle, with $G(0) = 0$ . The first drop can be at most $T_{d-1} + 1$ floors above the ground, because a break leaves the floors below it to two eggs with $d - 1$ drops, and those handle at most $T_{d-1}$ floors. If the egg survives, three eggs and $d - 1$ drops remain for the floors above. So

G(d) = T_{d-1} + 1 + G(d - 1),

and a plan built on these steps achieves it. The values are in the table.

Drops $d$	Two eggs, $T_{d-1}$	Three eggs, $G(d)$
1	0	1
2	1	3
3	3	7
4	6	14
5	10	25
6	15	41
7	21	63
8	28	92
9	36	129

Eight drops handle only 92 floors, and nine handle 129, so the fewest is 9 drops. One good first drop is floor 37. A break leaves floors 1 to 36 to two eggs with 8 drops, which is exactly the building of question 1, and survival leaves 63 floors to three eggs with 8 drops, fewer than 92. The third egg saves five drops compared with two eggs.