Sunday, 23 June 2013

The Eggy Mattress Puzzle

Excellent little puzzle from Puzzle Man Dave.

You're standing outside a 120-storey building, which has a mattress on the ground outside it. You have two identical eggs; and what you want to know (for no doubt excellent, but irrelevant, reasons) is the highest floor at which you can drop an egg out of the window and have it land on the mattress without breaking. You don't mind getting your mattress a bit eggy in the process, but you need a way of guaranteeing to find the highest floor.

Obviously even if you just had one egg then you could still find out the answer: you'd drop it out of the first floor, and if it didn't break, then you'd go for the second floor, and then the third, until it smashed. That would be the only procedure that would guarantee to discover the answer: if you started by dropping it out of floor five, for instance, and it broke, you'd have no idea whether it would have broken from floor four, and you'd be out of eggs. It works, but in the worst case it takes 120 drops.

But if you have two eggs, you can do better than that. You can guarantee to find out the answer in many fewer than 120 drops.

What's the optimal method, the one that guarantees to find the highest floor at which an egg won't break, but minimizes the number of drops required in the worst case?