Egg Dropping

Answer: 14 drops.

Let’s work our way up to a solution. As we’ve seen from the hints, once the device has broken, you will need to brute force ALL the remaining floors in the worst case scenario. But how do we optimise this then?

First, let’s start with a simpler version of the problem with 6 floors and 2 devices. We’ll start with a naive solution for now:

• First drop: Drop from floor 3.
  • If it breaks, test floor 1, then 2. Worst case: 3 moves.
  • If it doesn’t break, drop from floor 6.
    • If it breaks, test floor 4, then 5. Worst case: 4 moves.
    • If it doesn’t break, then we know the device survives all 6 floors.

This gives us a worst case of 4 moves.

Let’s come up with a way to visualise this. We indicate the drops with device 1 on a horizontal line. We start from the left point, and each step to the right indicates a drop.

When the device breaks on a specific floor, we can no longer make a horizontal step, so we must now take vertical steps downward. From hint 2, we know that once we’re left with 1 device, we must test all the floors sequentially. If the device breaks at floor 3, we need to test floors 1 and 2. If the device breaks at floor 6, we need to test floors 4 and 5. This gives us the following diagram:

We can see from this diagram that we have a worst-case of 4 moves (Start → 3 → 6 → 4 → 5). Can we do better? Let’s try a different strategy:

• First drop: Drop from floor 2.
  • If it breaks, test floor 1. Worst case: 2 moves.
  • If it doesn’t break, drop from floor 4.
    • If it breaks, test floor 3. Worst case: 3 moves.
    • If it doesn’t break, test floor 6.
      • If it breaks, test floor 5. Worst case: 4 moves
      • If it doesn’t break, then we know the device survives all 6 floors.

Hmm, we’re still stuck with a worst-case of 4 moves (Start → 2 → 4 → 6 → 5). But does that mean we’ve found the optimal number of drops?

No! Notice how in both versions of the diagram, we have short paths that terminate early. In version 1, we have (Start → 3 → 1 → 2) and (Start → 3 → 6 without breaking). In version 2, we have (Start → 2 → 1), (Start → 2 → 4 → 3), and (Start → 2 → 4 → 6 without breaking). If we could make these longer in order to shorten the worst-case path, we’ll find a better solution. And in fact, we can!

• First drop: Drop from floor 3.
  • If it breaks, test floor 1, then 2. Worst case: 3 moves.
  • If it doesn’t break, drop from floor 5.
    • If it breaks, test floor 4. Worst case: 3 moves.
    • If it doesn’t break, test floor 6. Worst case: 3 moves.

No matter which path we take, we’ll always end up with 3 moves in the worst case.

With this visualisation in mind, let’s explore some solutions for the 100-storey version of the puzzle. In hint 3, we offered a naive solution of dropping from the 50th floor. Visualising it with our new diagram, it looks like this:

Oof, that’s rough. It seems like we’re not taking proper advantage of the first device (the rightward movement on the diagram). So instead of making such huge jumps with the first device, we should instead move it in smaller steps.

How about steps of 10? This time, we’ll try dropping the first device from floor 10, then 20, then 30, and so on. At the first floor that it breaks on, we will test the remaining floors in between the last 2 drops. For example, if the first device breaks on floor 60, then we will drop the second device from floor 51, 52, ..., 59. Our diagram now looks like this:

In the worst case scenario, we have 19 moves (Start → 10 → 20 → 30 → 40 → 50 → 60 → 70 → 80 → 90 → 100 → 91 → 92 → 93 → 94 → 95 → 96 → 97 → 98 → 99). But notice how the shorter chains have only 10 moves, 11 moves, and so on? Let’s lengthen them. Instead of having the first drop at 10, we can have the first drop at 14 (a jump of 14). Then our next jump should be $14+13=27$14+13=27. Then the following drop should be $27+12=39$27+12=39. Continuing this way, we get a chart of:

In the worst case scenario, we have 14 moves, and we can’t do any better than this. However, through this diagram, we see that for a maximum of 14 moves, this strategy works up to a maximum building height of 105 storeys.