Dinosaur Egg Drop v2

Question

This question is a little different and kinda follow-up version of Dinosaur Egg Drop

1- You have 100 story building and 6 Apatosaurus dinosaur eggs.

2- You have 81 story building and 3 Massospondylus dinosaur eggs.

In both cases, you would like to find these different kind of dinosaur eggs durabilities (I don't know why you need to test it though, crazy scientists).

So at least how many times do you need to drop the eggs to find at which highest floor the eggs do not break in the worst case scenario for each case?

Answer 1

Even if the generalised question is already answered by Mike Earnest, let me put here this method which reaches the same conclusion without a recursive approach

Let me rephrase the question into the following form (just as Mike did):

Given $eggs$ number of eggs with identical durability, and $throws$ number of maximal attempts, what is the maximal number of stories for which we can identify the durability?

If we note this value with $stories(eggs,throws)$, the original two questions can be rephrased as: what is the smallest value of $throws$, for which

1. $stories(6,throws)\ge100$;
2. $stories(3,throws)\ge81$?

Sure $stories(eggs,throws)$ can be found by solving the recursion, but there is another way to do that: the results of the sequence of our attempts can be coded by binary sequences that indicate if an egg was broken (marked with 1) at an attempt or not (marked with 0).
A possible code is either

• exactly $throws$ digits long, with at most $eggs-1$ of them being 1s (marking the cases when we ran out of attempts, but had eggs left), or
• at most $throws$ digits long, the last one being 1 and another $eggs-1$ being 1 as well (marking the cases when we ran out of eggs).

So for example if we had 5 attempts and 2 eggs, possible codes look like 00100 (the egg thrown on the third attempt broke), or 011 (the eggs thrown on second and third attempts broke, leaving us with no more eggs).

An optimal strategy results in different codes belong to different durabilities. So the question got reduced to how many different codes are there?

The first type gives: $\sum\limits_{i=0}^{eggs-1}\binom{throws}{i}$, the second type gives: $\sum\limits_{j=eggs}^{throws}\binom{j-1}{eggs-1}=\binom{throws}{eggs}$.

At this point it is worth noting, that the all-0 word is not a valid code, as it does not allow us to determine the durability. In practice it means, that even if we throw an egg from the topmost story, it does not break. Excluding it means that the first sum's term of $i=0$ is removed.

Adding these together we get $\sum\limits_{i=1}^{eggs}\binom{throws}{i}$.

This is already the very same expression that Mike had, so no wonder, that the actual cases give the same results:

1. The minimal $throws$ value for which $\sum\limits_{i=1}^{6}\binom{throws}{i}\ge100$ is 7:
   for 6 the expression gives $\sum\limits_{i=1}^{6}\binom{6}{i}=2^6-\binom{6}{0}=63$;
   for 7 it is $\sum\limits_{i=1}^{6}\binom{7}{i}=2^7-\binom{7}{0}-\binom{7}{7}=126$.
2. The minimal $throws$ value for which $\sum\limits_{i=1}^{3}\binom{throws}{i}\ge81$ is 8:
   for 7 the expression gives $\sum\limits_{i=1}^{3}\binom{7}{i}=\binom{7}{1}+\binom{7}{2}+\binom{7}{3}=63$;
   for 8 it is $\sum\limits_{i=1}^{3}\binom{8}{i}=\binom{8}{1}+\binom{8}{2}+\binom{8}{3}=92$.

Answer 2

More generally, suppose there are $e$ eggs, and you only have time for $d$ drops. What is the tallest building for which you can succeed? Like all good questions, this one is answered using Pascal's Triangle.

Given $e$ eggs and $d$ drops, the largest building for which you can succeed is one with $$\binom{d}1+\binom{d}2+\dots+\binom{d}{e}$$floors. This is equal to the sum of the first $e$ entries in the $d$th row of Pascal's triangles, skipping over the first entry (which is always a 1).

1. With 100 floors and 6 eggs, the optimal number of drops is 7. 7 drops is enough since the sum of the first 6 entries in the 7th row is 7 + 21 + 35 + 35 + 21 + 7 = 126 ≥ 100. 6 drops is not enough since looking at the 6th row, 6 + 15 + 20 + 15 + 6 + 1 = 63 < 100.

2. With 81 floors and 3 eggs, it will take 8 drops, since 8 + 28 + 58 ≥ 81, but 7 + 21 + 35 < 81.

---

 Modified Pascals's triangle (left side of ones removed).

                        1
                     2     1
                  3     3     1
               4     6     4     1
            5    10    10     5     1
         6    15    20    15     6     1
      7    21    35    35    21     7     1
   8    28    56    70    56    28     8     1

I'll provide a proof sketch. Letting Opt(d,e) be the number of floors you can handle with d drops and e eggs, then $$Opt(d,e) = 1+ Opt(d-1,e)+Opt(d-1,e-1)$$ Why? If you can succeed, there must be at most Opt(d-1,e) floors above the floor you drop from, because if the egg survives you have d-1 drops and e eggs remaining. Similarly, there must be at most Opt(d-1,e-1) floors below in case the egg breaks. If you can succeed, the total number of floors is then then at most the sum of those two numbers, plus 1 for the floor you dropped from. The above equation then allows you to prove the $\binom{d}1+\binom{d}2+\dots+\binom{d}{e}$ formula by induction on $d$.

In general, if you have $f$ floors, the strategy is to drop your egg from floor number $1+\binom{d-1}1+\binom{d-1}2+\dots+\binom{d-1}{e-1},$ where $d$ is the smallest number such that $\binom{d}1+\binom{d}2+\dots+\binom{d}{e}\ge f$.

Answer 3

1 – A 100-story building and 6 Apatosaurus dinosaur eggs.

The maximum height can determined with 7 drops.

Actually, up to 126 stories can be determined with the same number of drops and Apatosaurus dinosaur eggs.

2 – An 81-story building and 3 Massospondylus dinosaur eggs.

The maximum height can determined with 8 drops.

Actually, up to 92 stories can be determined with the same number of drops and Massospondylus eggs.

In the following worksheet, two rules are followed to determine each entry from entries to its left and above.

• For drops < eggs, it is the same as having fewer eggs, straight down from the previous row.

• For drops ≥ eggs, the number of stories can be calculated by looking on the same row and the row above.
       1 story + [stories with drops-1 and same eggs (same row, previous column)]
           + [stories with drops-1 and eggs-1   (previous row, previous column)]

 Maximum number of stories                          drops
 that can be determined                     1  2  3   4   5   6   7  8
                                    eggs
                                      1     1  2  3   4   5   6   7  8
                                            :\  \  \   \   \   \
                                            : \  \  \   \   \   \
                                      2     1--3--6--10--15--21--28
                                            :  :\  \   \   \   \   \
                                            :  : \  \   \   \   \   \
                                      3     1  3--7--14--25--41--63--92
                                            :  :  :\   \
                                            :  :  : \   \
                                      4     1  3  7--15--30
                                            :  :  :   :\   \
                                            :  :  :   : \   \
                                      5     1  3  7  15--31--62
                                            :  :  :   :   :\   \
                                            :  :  :   :   : \   \
                                      6     1  3  7  15  31--63--126