Puzzle – A safe place to drop an egg

This is a problem where it’s fairly easy to find the solution via trial and error, but not so easy to generalize.

Question

Let’s say you need to find out the highest floor in a 100 story building from which you could safely drop an egg without it breaking. What’s your strategy to minimize the worst case number of drops you have to try?

If you just had one egg with which to conduct your experiment, you’d have to start at floor one, and go up floor by floor looking for the first floor at which your egg broke until you reached floor 100. So your maximum number of drops would be 100.

What would be the worst case number of drops if you could use two eggs?

Answer

With two eggs you can be cleverer, and drop the first egg at floor 50, and effectively divide the floor space in half for your second egg.

You could also drop the first egg at floor 10, then assuming it doesn’t break, floor 20, 30, and so on. As soon as it broke, you’d try the 9 floors underneath with your second egg. So worst case if you get all the way to floor 100 before it breaks, then start at floor 91 with the second egg and get all the way to floor 99, then the total worst case drops is 19.

Can we do better?

Picking 10 as number of floors to skip with the first egg is not particularly efficient in dividing the floor space because if the first egg breaks on floor 10, the worst case is 10. But if the first egg breaks on floor 20, then the worst case is 11. As we saw, by the time you get to floor 100 your worst case is 19. The most efficient solution will be when no matter where the first egg breaks, our worst case stays the same.

To do that we could say that we’ll start with our first egg at floor 10, but the second drop will be on floor 19, preserving our 10 drop worst case. The problem you’ll find is that you end up reducing the spacing to 1 before you get anywhere close to floor 100. By trial and error you can find the best number to start with, and it turns out to be 14, giving us a 14 drop worst case:

14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100.

Generalization

Is there a formula we can use to work this out, so we could do it for any number of floors?

Let’s look at the number of floors we skip at each turn:

n, n-1, n-2, n-3 … 1

Flipping that around, we have:

1, 2, 3, 4….. n.

We also know that the sum of the number of floors skipped will equal the total number of floors.

We know that the sum of a sequence like the above is (n+1) * n/2. You can see this if you pair the first and last numbers, the the second and second to last, etc.

So if we say h is the total number of floors in the building, we have:

h = (n+1) * n/2

So:

n^2 + n = 2h.

To solve for n, let’s use the completing the square trick:

n^2 + n + .25 = 2h + .25
(n+.5)(n+.5) = 2h + .25
n+.5 = sqrt (2h+.25)
n = sqrt(2h+.25) – .5

If we try this on our 100 floor problem, we get:

n = sqrt(200.25)-.5
n=13.65

So seeing as we need integer floors, we need 14 floors, which corresponds with our trial and error result.

I have to give props to Scruffy Pete for helping out on this one.