Imagine you're a farmer and you've produced a breed of hen that lays particularly strong eggs. You want to test just how strong those eggs are by throwing them off the various floors of a 100-story building. Your task is to find the highest floor you can drop an egg from without breaking it. If you had just one egg, you'd know how you would do this: first throw the egg off the 1st floor, if it doesn't break move up to the second, then the third, and so on. You'd need at most 100 throws to find the answer.

But now suppose you had two eggs. What strategy would you use to find the highest drop an egg can survive? What's the smallest number of egg throws you can get away with?

Solution

Let's assume that the best strategy — the strategy for which the maximal number of drops needed is as small as possible — starts with throwing the first egg off the $nth$ floor. It has to start somewhere, after all, so we might as well call that starting floor $n.$ Notice that, if the first egg breaks on that first drop, we are back in the one-egg scenario: we have no choice but to test the $n-1$ floors below one by one using the second egg, and that could take up to $n-1$ drops. Therefore, the maximal number of drops needed for our strategy is at least $n.$ There's no way of getting away from that fact: a strategy that starts on the $nth$ floor can require up to $n$ drops (if not more). Now suppose that the first egg doesn't break when dropped from the $nth$ floor. We should now drop our still-intact first egg from some higher floor, but which one? It would be good to skip a whole chunk of floors so that if the first egg doesn't break on the second drop either, we have eliminated that large chunk in one go. On the other hand, we don't want that chunk to be too large: if the first egg does break on the second drop, we need to test that whole chunk floor by floor, using the second egg. So let's choose the size of the chunk to be as large as we can get away with without making the lower bound of the maximal number of drops needed any larger than it already was — that is, without making it greater than $n.$ Since we will have already used $2$ drops with the first egg, we only have $n-2$ left. Let's therefore move up by another $n-1$ floors for our second drop with the first egg. If it breaks, then we need to check at most $n-2$ floors (the floors between $n+1$ and $n-2$ inclusive) with the second egg. The maximal number of drops needed is still at least $n,$ no matter if the first egg drops on the first or on the second drop. By the same reasoning, we should move up another $n-2$ floors for the third drop of the first egg, then another $n-3$ floors for the fourth drop, and so on. Since there are 100 floors in total, our number $n$ needs to satisfy the equation $$n + (n-1) + (n-2) + .... + 2 + 1 = 100.$$ Now it turns out that $$n + (n-1) + (n-2) + .... + 2 + 1 = \frac{(n+1)n}{2},$$ so we need $$\frac{(n+1)n}{2} = 100,$$ which means that $$n^2 + n - 200 = 0.$$ Solving this quadratic equation gives a positive solution of $$n=\frac{-1 + \sqrt{801}}{2} \approx 13.65.$$ We need a whole number solution, so we'll round that up to $14.$ Therefore, the best strategy starts with dropping the first egg off the 14th floor, if it doesn't break moves up to the $14+13 = 27th$ floor, then to the $14+13+12=39th$ floor and so on. When the first egg breaks, the strategy tests all the floors in the chunk below one by one using the second egg. The maximal number of drops needed is $14.$