You have 2 identical eggs and a 100 floor building. An egg breaks if dropped from any floor above an unknown threshold and survives at or below it. A broken egg cannot be reused, and eggs that survive can be dropped again. What is the smallest number of drops that always finds the threshold, and what floor do you try first?

You have 2 identical eggs and a 100 floor building. An egg breaks if dropped from any floor above an unknown threshold and survives at or below it. A broken egg cannot be reused, and eggs that survive can be dropped again. What is the smallest number of drops that always finds the threshold, and what floor do you try first?

Approach: Fix a drop budget and note that after the first egg breaks the second must be walked up one floor at a time, so the gaps between first egg drops have to shrink by one each time.

14. With a budget of k drops, the first egg goes to floor k. If it breaks you have k - 1 drops and k - 1 unknown floors below, which the second egg walks one at a time. If it survives, the next gap must be k - 1, then k - 2, and so on, so the height covered is the triangular number k(k+1)/2. Since 13 * 14/2 = 91 falls short of 100 and 14 * 15/2 = 105 clears it, the answer is 14 and the first drop is floor 14, then 27, 39, 50, 60, 69, 77, 84, 90, 95, 99 and 100. Binary search is the wrong instinct: a break at floor 50 leaves 49 candidate floors and one egg, forcing 50 more drops in the worst case.

Follow-up: With 3 eggs and 100 floors, what is the smallest worst case number of drops?

Key concepts: worst case analysis, triangular numbers, search strategy.