A two - egg puzzle
Suppose there is a building of height n floors, and that there is a maximum height, h, (in floors) from which an egg can be dropped without breaking. For simplicity, assume this value is constant for all eggs. You have two eggs with which to determine this height h. An egg dropped from height h or below will not break and can be reused, while an egg dropped from a height greater than h will break and cannot be reused. Determine, with proof, a strategy to minimize the maximum possible number of drops used to determine h. What is the minimax number of drops, d as a function of n?

Solution
Consider the problem from the other side. Let g(d) be the maximum height of a building for which we can determine h using at most d drops. That is to say, if h is limited to being between 0 and g(d) (inclusive), then we can solve the problem in d (or fewer) drops. Clearly, g(1)=1 as if we only have one drop, either the egg breaks or it doesn't so we can only determine if h is 0 or 1.

Suppose we know g(d) for some value of d and we wish to determine g(d+1). Note that if we drop the first egg from floor i and it breaks, then we must drop the second egg from each of the floors below i from the bottom up. This uses a total of i drops, and we have d remaining, so the first drop is from height at most d+1. If the first egg survives, then we essentially have the same problem starting at the next floor up, and we know that we can determine h if it is at most g(d). Thus, starting as high as possible on the first drop we have g(d+1) = g(d)+d+1. It is an easy inductive proof to show that g(d) is the d^th triangular number d(d+1) / 2.

To determine f, we note that f(n) is the least value of d such that g(d) ≥ n. In terms of triangular numbers, f(n) is the index of the first triangular number at least as large as n. If you want a real formula, we consider:

d(d+1) / 2 ≥ n
d² + d - 2n ≥ 0

Solving the quadratic for being equal to zero gives d = 1/2 × (-1± √(8n+1)). Obviously we want d to be positive and we want the next higher integral value of d so for our answer we obtain: d = ⌈ (√(8n+1) - 1) / 2 ⌉

The strategy part was discovered earlier, after determining d, drop the first egg from floor d. If it breaks, drop it from floors 1, 2, and so on until it breaks and you know h. If The egg survives the first drop, consider the other n - d floors to be a building and solve it in d - 1 drops.
Back to the Puzzles page.