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?
I have an algorithm whose worst case scales as O(sqrt(n)) for some maximum floor , with a worst case of 20 drops. It is in fact O(n^(1/m)), for m eggs, and requires approximately 2 * n^(1/m) drops. I think.
ReplyDeleteErg, edit fail. 'for some maximum floor count n', 20 is worst case for 120 floors.
Delete20 is not bad, but you can do better. You're right that it's quadratic.
DeleteOn the other hand, if you mean real eggs and mattresses, and not theoretical puzzle-eggs and puzzle-mattresses, I would temper my algorithm to ignore floors above 4, because real eggs would smash from floor 1 or 2, let alone 5. That algorithm requires 3 drops in the worst case, however many eggs or floors.
ReplyDeleteThe more serious problem is that eggs reach terminal velocity after about five floors.
DeleteIf you want to make the problem realistic, it's easily done. You're standing on the moon, outside a 120-storey building...
(If you're on the moon, you might not even need the mattress.)