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 F_{1}, F_{2}, F_{3}, 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 D_{1} drops with the first marble and D_{2} drops with the second, then the total number of drops is D = D_{1} + D_{2}. That’s what we want to minimize. The enemy will always make D_{2} as large as he can by picking a floor that’s one of the F_{n} drops. So if the first marble breaks at F_{6} (D_{1} = 6), you have to backtrack to F_{5} and go in increments of one floor until F_{6} − 1, where it still won’t break, and you know F_{6} is your answer (D_{2} = F_{6} − F_{5} − 1). The enemy won’t choose any floor between F_{5} and F_{6} since that’s sure to result in a lower number of total drops than simply picking F_{6}.
If there’s one F_{n} 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 D_{2}). We can keep doing that with the “most expensive” F_{n} until all F_{n}’s have the same total number of drops.
For the cost (D = D_{1} + D_{2}) of each F_{n} to be the same, we need to decrease each successive F_{n}’s D_{2} by one to compensate for each increase of D_{1} (to keep D the same). Since D_{2} is the difference between successive levels, the distance between the F_{n}’s decreases by one for each level. For example, if F_{1} = 10, then:
First-marble Drops | D_{1} | Worst-case D_{2} | D |
---|---|---|---|
F_{1} = Floor 10 | 1 | 9 (floors 1–9) | 10 |
F_{2} = Floor 19 | 2 | 8 (floors 11–18) | 10 |
F_{3} = Floor 27 | 3 | 7 (floors 20–26) | 10 |
F_{4} = Floor 34 | 4 | 6 (floors 28–33) | 10 |
So now we have to figure out the first floor (F_{1}). That will tell us the rest of the floors to test. If we pick F_{1} too low, we won’t make it all the way to our target N = 100 flights. Say if we pick F_{1} = 5, then we’ll test flights 5, 9, 12, 14, 15, and that’s it. If we pick F_{1} too high, like F_{1} = 50, then we’ll do way too many drops (50). So there’s some minimum F_{1} that will allow us to reach N = 100.
Our series F_{1}, F_{2}, F_{3}, . . . 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 F_{1}. So the last floor is the sum of the first F_{1} integers. The formula for the sum of the first M integers is (M×(M + 1))/2. So we want (F_{1} × (F_{1} + 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 F_{1} 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 F_{1} we get F_{1} × (F_{1} + 1) = 198, F_{1}² + F_{1} − 198 = 0, and using the quadratic formula we get F_{1} = 13.6. We round up and get F_{1} = 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.