Tuesday Teaser #5
I’m in a building with 20 floors and I have two laptops. I want to know the highest floor from which I can drop a laptop without it breaking. For the purposes of the puzzle, the laptop either breaks or works after each drop. Obviously after a laptop breaks, it can no longer be used, so I’m down to one. What is the least number of drops needed to identify the maximum height?
I had this problem in my algorithms design class, so let’s reframe the question in terms of worst-case complexity. Let p denote the lowest floor that a laptop will break on. To minimize drops we will drop the first laptop on spaced intervals to determine a upper bound for p and use the second laptop to find the precise value for p.
The task now is to find the best interval size k to work with. Suppose k = 10, then in the worst case p = 19 or 20 will require drops at 10, 20 (breaks), and drops for each floor from 11 and 19. If k = 10, we require at most 11 drops. We need to do better.
If k = 4, we drop the first laptop at floors 4, 8, 12, 16, 20, and if it breaks at any of these intervals, we test with the second laptop in the 3 floors below. In the worst-case p = 19 or 20, we have to do drops on 4, 8, 12, 16, 20 (break), 17, 18, 19. This gives 8 drops.
If k = 5, then the worst case of 19 or 20 requires drops on 5, 10, 15, 20 (break), 16, 17, 18, 19. This gives 8 drops.
I’m too lazy to do an average case analysis for k, but we can conclude that we can identify the maximum height in 8 drops or less.
