mathematics - Dinosaur Egg Drop v2

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

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