mathematics - Dinosaur egg drop

Archeologists discover two dinosaur eggs, and you are given the chance to test the durability of these eggs (bad move on their part). Suppose that these eggs will absorb a specific amount of force with no cumulative damage. In other words, if they don't crack, it is as if they never fell.

You have a 100 story building, and you are allowed only 20 trials.

Questions:

1. Is there an algorithm such that you can determine the highest floor in which one of these dinosaur eggs can be dropped and not break?


2. If so, what would be the highest building for which this algorithm would be able to work?


3. Supposing the number of trials were still 20, but you had as many dinosaur eggs as you needed. At what point would extra eggs not increase the highest floor for which you can test?

Bonus question:

4. What would be the highest building you could test for with 3 eggs at your disposal?

Answer

1. 
   

   
   

   Take the first egg. Drop it from floors 10, 20, 30, ..., 100 until it breaks. This will take at most 10 of the 20 trials. When it breaks, go 9 floors down, and test every floor with the remaining egg. E.g. if the first egg breaks at 70, drop the second egg from 61, 62, 62, ..., 69. That's at most 19 trials in total.

   
   

   
   


2. 
   

   
   

   We can do a bit better though. If the first egg breaks on the first trial, we've got 19 trials left, so we can actually drop it from the 20th floor right away, because there are enough remaining trials to test each floor below. If it doesn't break, we can go 19 floors up for the second trial (with the same egg). Continuing like this, we might be lucky to be using the first egg for all 20 trials without risking not having enough trials to figure out the exact floor. This means we can go up to 20 + 19 + 18 + ... + 1 = 210 floors, using

   
   

   
   
   

This:

$$ \sum_{n=0}^{19} n+1 = \sum_{n=1}^{20} n = \frac{20(20+1)}{2} = 210. $$

Just to break down the first version of this:

There are 20 possibilities for when the first egg breaks. For each case $n$ is the number of trials left. And for each such case we can test $n$ floors with the second egg and $1$ floor with the egg we potentially broke. Hence the summand of $n+1$.

3. 
   

   
   

   With more eggs, you can can basically apply a binary search, halving the potential range of floors each time. That lets you check 2²⁰ = 1048576 floors. The first egg is dropped from floor 2¹⁹, then you go up or down 2¹⁸ floors depending on whether the egg broke on the first trial.

   
   

   
   


4. 
   

   
   

   With three eggs, we can test considerably more than with two eggs. Consider the first egg breaking on the first trial. Then we've got 19 trials and two eggs left. Applying algorithm 2, we can still test 190 floors with those. So we can drop the first egg from floor 191. If the first egg breaks on the second trial, we've still got 18 trials and two eggs left, with which we can test 171 floors, so we can make the second trial already from floor 373, and so on. This holds as long as there are at least two trials left, so that we can make use of both eggs. If we're still dropping the first egg on trial number 19, then we've only got one trial left, so we can only go up two floors for the 19th trial. I think this coincides with the previous formula, but I'm not sure it would if we generalise this beyond 3 eggs. Basically, for the last two trials, this reduces to the above formula.

   
   

   
   
   

So we have with 3 eggs:

$$ \sum_{m=1}^{18}\left(1+\sum_{n=0}^m n+1\right) + \sum_{n=0}^{1} n+1 = 1350 $$