7
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ So we have unlimited trials but trying to find the minimum with a limited amount of eggs? $\endgroup$ – Beastly Gerbil Feb 25 '17 at 15:52
  • $\begingroup$ @BeastlyGerbil yes $\endgroup$ – Oray Feb 25 '17 at 16:45
7
$\begingroup$

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$.
$\endgroup$
  • $\begingroup$ ^vote with a note: When there's an opportunity, it would be nice to see explicit application carried through with the cases in question $\endgroup$ – humn Feb 25 '17 at 17:49
  • 2
    $\begingroup$ This is very insightful! I like this better than my answer, it was great to see what the formula actually means. $\endgroup$ – Mike Earnest Feb 25 '17 at 18:11
  • 1
    $\begingroup$ Thanks, @MikeEarnest! Fun fact: the number of codes with a given prefix is closely related to which story you should throw the eggs according to the optimal strategy. For example $eggs=3$ and $throws=8$ has 28 codes starting with 1 so you should drop your first egg from story 29. $\endgroup$ – elias Feb 25 '17 at 18:22
  • 1
    $\begingroup$ Thanks, @Oray, it was a great puzzle. I first heard a 2-egg variant of it during my university years, and someone told me that there is an answer involving the toolset of Information Theory, but I've never heard the actual solution using that. Back then I solved it with the method using recursion. This new idea just hit me during I typed my answer including the recursion, and reminded me of the puzzle with the poisoned bottle of wine, which can be bruteforced with recursion, but can also be solved in one line with a similar coding-approach. $\endgroup$ – elias Feb 25 '17 at 18:30
  • 1
    $\begingroup$ Word of caution: there are problems in which full utilization of codes is not possible; in general you would also need to show that a strategy that allocates different values to different codes exists. $\endgroup$ – ffao Feb 27 '17 at 4:24
8
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Ah, you ninja'd me with this one. Great work! However, I still have a note to add and will do it in my answer. $\endgroup$ – elias Feb 25 '17 at 17:03
  • $\begingroup$ No votes of approval for an answer that got there 19 minutes earlier? $\endgroup$ – humn Feb 25 '17 at 17:21
  • $\begingroup$ @humn this is a different answer, which uses different mathematics and gets the answer for all. You may have got the answer, but this has solved the problem $\endgroup$ – Beastly Gerbil Feb 25 '17 at 17:27
  • $\begingroup$ They have essentially the same reasoning, @Beastly Gerbil, with identical induction formulas, and both solve the general case. $\endgroup$ – humn Feb 25 '17 at 17:45
5
$\begingroup$

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  

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.