Can you solve the egg drop riddle?
The city has just opened its one-of-a-kind Fabergé Egg Museum with a single egg displayed on each floor of a 100-story building. And the world’s most notorious jewel thief already has her eyes on the prize. Because security is tight and the eggs are so large, she’ll only get the chance to steal one by dropping it out the window into her waiting truck and repelling down before the police can arrive.
All eggs are identical in weight and construction, but each floor’s egg is more rare and valuable than the one below it. While the thief would naturally like to take the priceless egg at the top, she suspects it won’t survive a 100-story drop. Being pragmatic, she decides to settle for the most expensive egg she can get. In the museum’s gift shop, she finds two souvenir eggs, perfect replicas that are perfectly worthless.
The plan is to test drop them to find the highest floor at which an egg will survive the fall without breaking. Of course, the experiment can only be repeated until both replica eggs are smashed. And throwing souvenirs out the window too many times is probably going to draw the guards’ attention. What’s the least number of tries it would take to guarantee that she find the right floor? Pause here if you want to figure it out for yourself! Answer in: 3 Answer in: 2 Answer in: 1 If you’re having trouble getting started on the solution, it might help to start with a simpler scenario.
Imagine our thief only had one replica egg. She’d have a single option: To start by dropping it from the first floor and go up one by one until it breaks. Then she’d know that the floor below that is the one she needs to target for the real heist. But this could require as many as 100 tries. Having an additional replica egg gives the thief a better option. She can drop the first egg from different floors at larger intervals in order to narrow down the range where the critical floor can be found.
And once the first breaks, she can use the second egg to explore that interval floor by floor. Large floor intervals don’t work great. In the worst case scenario, they require many tests with the second egg. Smaller intervals work much better. For example, if she starts by dropping the first egg from every 10th floor, once it breaks, she’ll only have to test the nine floors below. That means it’ll take at most 19 tries to find the right floor. But can she do even better? After all, there’s no reason every interval has to be the same size.
Let’s say there were only ten floors. The thief could test this whole building with just four total throws by dropping the first egg at floors four, seven, and nine. If it broke at floor four, it would take up to three throws of the second egg to find the exact floor. If it broke at seven, it would take up to two throws with the second egg. And if it broke at floor nine, it would take just one more throw of the second egg. Intuitively, what we’re trying to do here is divide the building into sections where no matter which floor is correct, it takes up to the same number of throws to find it. We want each interval to be one floor smaller than the last. This equation can help us solve for the first floor we need to start with in the 100 floor building.
There are several ways to solve this equation, including trial and error. If we plug in two for n, that equation would look like this. If we plug in three, we get this. So we can find the first n to pass 100 by adding more terms until we get to our answer, which is 14. And so our thief starts on the 14th floor, moving up to the 27th, the 39th, and so on, for a maximum of 14 drops. Like the old saying goes, you can’t pull a heist without breaking a few eggs.
Responses