Egg Drop to 100
There is a new type of single-egg container to test. You are given a container, two eggs, and access to a one hundred-story building. You want to see how high up you can drop an egg in one of these containers and not have the egg break.
You could simply drop an egg from each floor, starting with the first floor, and see where the egg breaks for the first time. However, if the containers are really good, that would mean one hundred egg drops. How can you find out how good the container is with fewer drops?
THE CHALLENGE
Find a method that uses the fewest total number of drops, no matter how good or bad this new container is, to discover the highest floor in this one hundred-story building you can safely drop an egg from.
EXPLORATION
How would your strategy change if you had three eggs to work with?
Notes
THE CHALLENGE
In “Egg Drop – 1” we saw that using evenly spaced floors for the first round of tests reduced the total number of drops.
For example, if the first round involved dropping from multiples of ten, then the worst case would require 19 drops – 9 up to the 90th floor, and then single floor skips up to the 100th floor.
The big improvement comes from deciding to use variable-sized steps during the first phase. If you space them evenly, then by the time you have gotten near the top, you have all the tests to get up there and then a bunch of single-step tests after that. The key is to reduce the step size by one after each test during the first phase.
While you can figure out the first step size mathematically, it is easy enough to do by trial and error. If you start with a step size of 12 and decrease it by 1 each time, you will have steps of size 12 + 11 + 10 + …. + 1 = 78, and you will not get to the top. You need to start with a step size of 14 to make it. Now, the worst case is 14 drops, which is a big improvement!
EXPLORATION
Using three eggs gets tricky. Each time you add a new egg, you want to take advantage of knowing the best way to use the earlier collection of eggs. For example, when using two eggs, you know that after the first egg fails you will be testing in single steps.
Doing 3 eggs rigorously takes an unreasonable amount of math for an elementary school student. However, we can substitute some trial and error and still get the answer reasonably quickly.
Let’s start by knowing these sums (called triangular numbers): 1 + 2 = 3, 1 + 2 + 3 = 6, 1 + 2 + 3 + 4 = 10, 1 + 2 + 3 + 4 + 5 = 15, 1 + 2 + 3 + 4 + 5 + 6 = 21, 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28, and 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36. We want to use these sums to guide our choices of initial tests. For example, if we start with28, and then use 28 + 21 = 49, and then go to 28 + 21 + 15 = 64, and so on, we won’t quite get to the top.
So, our first set of tests should be at 36, 36 + 28 = 64, 36 + 28 + 21 = 85, 36 + 28 + 21 + 15 = 100. That is, we will test at floors 36, 64, and 85. No matter how those tests go, the worst case scenario is that we will need 9 tests!
You may also enjoy showing your class the following video from TEDED:
https://ed.ted.com/lessons/can-you-solve-the-egg-drop-riddle-yossi-elran