A puzzle in a puzzle book
Wikipedia's egg-dropping section cites Konhauser, Velleman and Wagon's collection "Which Way Did the Bicycle Go?", published in 1996 by the Mathematical Association of America. The puzzle is on p. 53.
There is a 100-floor building and two identical eggs. Somewhere in it is a critical floor: an egg dropped from it or higher breaks, and from below it stays whole. An unbroken egg can be dropped again. You are looking for the highest floor from which an egg does not break, and you must find it for sure. How many drops do you need in the worst case if you play it best?
It looks as if you should halve the building (50 drops) or try every tenth floor (19 drops). But the first drop should be from floor 14, and each next jump one floor shorter: 14, 13, 12… Then any outcome is found in 14 drops, because 14 + 13 + … + 1 = 105 ≥ 100.
A classic interview puzzle for programmers: William Poundstone presents it as a Google interview question (2012), and in "Cracking the Coding Interview" it is problem 6.8. It tests not formulas but the habit of thinking about the worst case and counting the price of every failure.
100 floors, numbered 1 to 100. Somewhere there is a threshold: below it an egg survives the fall, from it and above the egg breaks.
Two identical eggs. An unbroken egg can be dropped again, and the fall does not weaken it. A broken egg is gone.
You must name the highest safe floor. It may be 0, if an egg breaks even from floor 1, or 100, if it survives even floor 100. That is 101 possibilities.
Every drop counts. The strategy may depend on what happened before, but it must work whatever the critical floor is.
What is the smallest number of drops that guarantees you find the highest safe floor?
"Binary search: drop from 50, then from 25 or 75…"
Binary search is great when eggs are unlimited. With two eggs, the first one broken at floor 50 leaves one egg for 49 floors, and they have to be checked one at a time: 50 drops. Dropping from every tenth floor gives 19. The best strategy gives 14, and nothing does better.
100 floors, two eggs, the best strategy. Lock in how many drops, in your view, guarantee the answer.
A breakdown of your answer will appear here.
Hard to decide? Open the hints one at a time: the easy one first, then stronger ones.
Binary search is the trap: once the first egg breaks, the second has to climb one floor at a time. Think about the worst case, not the typical one.
If the first egg breaks at floor x, you may need x − 1 more drops. So make each next jump of the first egg one floor shorter than the last.
Say the first drop is from floor d. If the egg survives, the next jump is d − 1 floors, then d − 2, and so on. How many floors can that cover, and which d does 100 need?
The critical floor is not fixed in advance here. The building decides whether the egg broke the moment you drop it, and always picks the answer that leaves you more work even if you play perfectly from then on. A ready-made strategy it knows in advance and plays against it. It does not cheat: every answer agrees with all the earlier ones. This is how we test exactly the worst case of your strategy.
Click a floor to drop an egg from it. Green stripe: the egg survived, red: it broke. Light floors are known to be safe, dark ones are known to break eggs.
The evil building shows the worst case. What if the critical floor is simply random? The chart shows how many drops each strategy needs for each of the 101 possible outcomes. The table compares the exact average with a simulation.
"Halving": the first egg goes to the middle of the untested stretch (50, 75, 88, 94…) until it breaks, then the second climbs one floor at a time. "Every 10th": 10, 20, 30… and then one at a time. After an egg breaks, the second always climbs from the last safe floor.
The key is not how fast you narrow the search but what each failure costs. While you have two eggs, a broken egg is no disaster. Once you have one left, every floor has to be checked on its own.
If the critical floor is random, both strategies spend about 10–11 drops on average. The difference shows up in the worst case: "every 10th" pays 10 drops with the first egg and 9 more with the second if the threshold is in the 90s. The best strategy evens out these costs so that no case is too expensive.
If the first egg breaks at floor x, the second must walk floors 1, 2, …, x − 1 one at a time: break it any other way and you never learn the answer. So a first drop from floor x can cost x drops. To fit into d drops, the first one must be no higher than floor d.
After the first drop survives, one drop is spent, so the second jump has d − 1 drops left and can be at most d − 1 floors long. The third is at most d − 2, and so on. With d = 14 the first egg falls from floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100.
The same count also proves that you cannot do better. With d drops the first jump is at most d floors, the second d − 1, …, the last 1. In total no more than 1 + 2 + … + d = d(d + 1)/2 floors. For d = 13 that is 91: not enough for 100 floors under any strategy. For d = 14 it is 105, with 5 floors to spare.
f(e, d) = f(e − 1, d − 1) + f(e, d − 1) + 1
f(e, d) = C(d, 1) + C(d, 2) + … + C(d, e)
The first drop splits the building into three parts: if the egg breaks, f(e − 1, d − 1) floors remain below for e − 1 eggs; if it survives, f(e, d − 1) remain above; plus the floor of the drop itself. That gives the recursion, and its solution is a sum of binomial coefficients: a row of Pascal's triangle cut after the e-th term. For one egg f = d, for two f = d(d + 1)/2, the triangular numbers. Marked cells: the first d that covers 100 floors.
Two eggs and d drops cover at most the sum of the first d whole numbers. It must be at least the number of floors N.
For N = 100: 13 is too few, 14 is enough.
The first egg's floors: jumps of 14, 13, 12, …, with the last one cut at 100.
In general, for e eggs: the smallest d at which the sum of binomial coefficients reaches N.
The 5 spare floors mean there is more than one optimal strategy: the first drop can be from any floor from 9 to 14 and still fit into 14. Below 9 it fails, because more than 91 floors would remain above, and two eggs have only 13 drops for them.
The eggs are only a prop. The puzzle is really about a search in which every failure has a price. In mathematics it grows into binomial sums, in logic it becomes a trade of failures for time, and in practice it tells you how to load-test a service or break specimens in a lab.
Mathematics
For 100 floors: one egg gives 100 drops, two give 14, three give 9, four give 8. With five it is already 7 drops, which is ⌈log₂ 101⌉, the limit of binary search: 7 yes-or-no answers tell apart at most 2⁷ = 128 cases, and there are 101. Beyond that, eggs no longer help.
Four eggs miss by a hair: f(4, 7) = 7 + 21 + 35 + 35 = 98 floors, two short. For large N, k eggs need about (k! · N)1/k drops: for two eggs and a million floors that is √2,000,000 ≈ 1,414, and the exact answer is 1,414 too.
Logic
The number of eggs is how many times you are allowed to fail, that is, to drop above the threshold. With no failure to spare you can only walk floor by floor. One spare failure lets you jump and cuts the time to about the square root of N. Each further failure takes another root, and once you can fail as often as binary search needs, the time falls to log₂ N.
It is a general trade: the cheaper a failure, the bolder the jumps you can take. Binary search is optimal only when failing costs nothing.
Practice
A service holds load up to some level from 0 to 1,000 and crashes above it. Every crash means a manual restart. How many crashes are you willing to put up with?
We look for the highest of 1,000 load levels the service survives. If it may crash only twice, it takes 45 tests, since 44 · 45/2 = 990 < 1,000 ≤ 1,035 = 45 · 46/2. The first test is at level 45, then jumps of 44, 43, … If it may crash as often as you like (a test environment restarts itself), binary search needs only 10 tests.
git bisect runs the same binary search: among 1,000 commits it finds the one that broke a program in about 10 steps, because a "bad" commit destroys nothing. In materials and crash testing, though, specimens are few and each costs money: a specimen that fails is a broken egg, so the tests are planned as stairs, as in this puzzle.
A related idea with binary codes is worked through in the poisoned wine and the rats.
Wikipedia's egg-dropping section cites Konhauser, Velleman and Wagon's collection "Which Way Did the Bicycle Go?", published in 1996 by the Mathematical Association of America. The puzzle is on p. 53.
Moshe Sniedovich devoted a paper to the puzzle, "The Joy of Egg-Dropping in Braunschweig and Hong Kong", in INFORMS Transactions on Education (vol. 4). It is number 4 in his "OR/MS Games" series on teaching games.
Wikipedia's article on dynamic programming uses a 36-floor building. That is the triangular number 8 · 9/2, so two eggs need exactly 8 drops, with not a single floor to spare.
On LeetCode, where programmers train for interviews, the general version with k eggs and n floors is problem 887, marked Hard.
With two eggs, 1,000,000 floors take 1,414 drops, since 1,414 · 1,415/2 = 1,000,405. With 20 eggs, 20 drops are enough, as in binary search.
In June 2013 Laszlo Bock, Google's head of People Operations, told The New York Times that "brainteasers are a complete waste of time… They serve primarily to make the interviewer feel smart." His examples, though, were estimation questions like how many golf balls fit in a plane.
Share your own explanation, an objection or a variant of the puzzle. You need a GitHub account to comment.
I keep adding new puzzles, new ways to explain them and write-ups of the discussions they start. Leave your email and I'll write when something new is out. No spam, one-click unsubscribe.
The sign-up form will appear here soon.