Puzzle: You are given two marbles and a 100 story building. There’s a floor where dropping a marble from that floor or any floor above it will cause the marble to break, but dropping a marble from any floor below it will not cause breakage. You want to devise an algorithm that will minimize the maximum number of drops needed to find that floor. With one marble, you can do no better than 100, but with two it is easy to improve on that. What is the fewest number of drops of the two marbles that will find the break floor, not knowing in advance where it is between 1 and 100?
(This puzzle is sometimes told with dropped mice or graduate students.)
Hint 1: Take large steps with the first marble, and when it breaks, backtrack to the previous step and increment by 1 with the second marble to find the precise floor.
Hint 2: The first marble must take smaller and smaller steps in order to keep its worst-case the same as that of the previous drop.
Answer: 14 drops
Solution: The general idea is to take large steps with the first marble, and when it breaks, backtrack to the previous step and increment by 1 with the second marble to find the precise floor. The question is, How do you take the large steps? I’ll call those floors F1, F2, F3, etc.
We can see this as an adversarial game where, once you pick your algorithm, the enemy picks the target floor to maximize your drops. Assuming that you take D1 drops with the first marble and D2 drops with the second, then the total number of drops is D = D1 + D2. That’s what we want to minimize. The enemy will always make D2 as large as he can by picking a floor that’s one of the Fn drops. So if the first marble breaks at F6 (D1 = 6), you have to backtrack to F5 and go in increments of one floor until F6 − 1, where it still won’t break, and you know F6 is your answer (D2 = F6 − F5 − 1). The enemy won’t choose any floor between F5 and F6 since that’s sure to result in a lower number of total drops than simply picking F6.
If there’s one Fn whose D (its “cost”) is greater than the others, our adversary will pick it. We can lower its number of drops by reducing its value (which will reduce its D2). We can keep doing that with the “most expensive” Fn until all Fn’s have the same total number of drops.
For the cost (D = D1 + D2) of each Fn to be the same, we need to decrease each successive Fn’s D2 by one to compensate for each increase of D1 (to keep D the same). Since D2 is the difference between successive levels, the distance between the Fn’s decreases by one for each level. For example, if F1 = 10, then:
| First-marble Drops | D1 | Worst-case D2 | D |
|---|---|---|---|
| F1 = Floor 10 | 1 | 9 (floors 1–9) | 10 |
| F2 = Floor 19 | 2 | 8 (floors 11–18) | 10 |
| F3 = Floor 27 | 3 | 7 (floors 20–26) | 10 |
| F4 = Floor 34 | 4 | 6 (floors 28–33) | 10 |
So now we have to figure out the first floor (F1). That will tell us the rest of the floors to test. If we pick F1 too low, we won’t make it all the way to our target N = 100 flights. Say if we pick F1 = 5, then we’ll test flights 5, 9, 12, 14, 15, and that’s it. If we pick F1 too high, like F1 = 50, then we’ll do way too many drops (50). So there’s some minimum F1 that will allow us to reach N = 100.
Our series F1, F2, F3, . . . must therefore stop just past 100. When I say “stop” I mean that the difference between successive floors is 1. So the difference between the last two floors is 1, then before that it’s 2, then 3, all the way down to F1. So the last floor is the sum of the first F1 integers. The formula for the sum of the first M integers is (M×(M + 1))/2. So we want (F1 × (F1 + 1))/2 + 1 = 100.
The “+ 1” there is subtle: it’s because if the last floor of our series doesn’t break the marble, then we know that the next floor is the floor that would have broken the marble (assuming that there are exactly that many floors and one of the floors will break the marble). For example, say F1 is 3. If it breaks at 3, we use the second marble to test floors 1 and 2 (for a total of 3 drops). If it doesn’t break at 3, we try floor 5. If it breaks at 5, we use the second marble to test at 4 (for a total of 3 drops when you include the drop at 3). If it doesn’t break at 5, you try at 6 (for a total of 3 drops, all with your first marble). If it doesn’t break at 6, you know that it’s floor 7 that would have broken it. So with 3 drops you can diagnose 7 floors. (With 6 floors you’re wasting your last drop at floor 6, since you know that must be the floor.)
Solving the above equation for F1 we get F1 × (F1 + 1) = 198, F1² + F1 − 198 = 0, and using the quadratic formula we get F1 = 13.6. We round up and get F1 = 14.
So the series of floors to test with the first marble is:
14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100
Once you find a floor that fails, go back to your previous floor and go up with your second marble. The worst case should be 14 drops.
Update 7/26/2009: Thanks to my friend Paul Rechsteiner for pointing out that I needed to add “+ 1” to the quadratic equation. Without it the solution for 100 floors is still correct, but it fails for 105 floors.