Dropping Eggs

First one can note that $n(0,p) = 0 = n(e,0), n(1,p) = p, n(p+a,p) = n(p,p) = 2^p - 1$ , for $a \geq 0$ , the latter inequality being that we can do a binary search for $x \in [0,2^p - 1]$ .

$n(e,p) = (n(e-1,p-1) + 1) + (n(e-1,p-2) + 1) + ... + (n(e-1,1) + 1) + (n(e-1,0) + 1)$ , as we can 1st test height $(n(e-1,p-1) + 1)$ , and if the egg breaks we run the method for $e-1$ eggs and $p-1$ parachutes on the $(n(e-1,p-1)$ discrete metres below.

Note, $n(1,p)$ is of order $O(p^1)$ . $n(2,p)$ is the sum of these, so is $O(p^2)$ . Similarly, we can see that $n(e,p)$ is $O(p^e)$ .

Looking at a table of differences for $n(e,p)$ across different values of $p$ : $\begin{matrix} p=0 && 1 && 2 && 3 & ... & e && e+1 & ...\\ n(e,0) && n(e,1) && n(e,2) && n(e,3) & ... & n(e,e) && n(e,e+1) & ... \end{matrix}$

.

Using $n(p+a,p) = n(p,p) = 2^p - 1$ :

$\begin{matrix} & p=0 && 1 && 2 && 3 & ... & e && e+1 & ...\\ \Delta_0 & 2^0 - 1 && 2^1 - 1 && 2^2 - 1 && 2^3 - 1 & ... && 2^e - 1 && n(e,e+1) & ... \\ \Delta_1 && 2^0 && 2^1 && 2^2 && ... & 2^{e-1} && ...\\ \Delta_2 &&& 2^0 && 2^1 && 2^2 & ...\\ \Delta_3 &&&& 2^0 && 2^1 && ...\\ &&&&& \ddots &&& \vdots \\ \Delta_e &&&&&& 2^0 && 2^0 && 2^0 & ... \end{matrix}$

Because $n(e,p) = O(p^e)$ the $\Delta_e$ row is all the same value, which will be $2^0 = 1$ .

The equation for $n(e,p)$ can be found by summing at the leftmost value of row $\Delta_i$ multiplied by $\binom{p}{i}$ .

Hence, $n(e,p) = \sum_{i=1}^{e} \binom{p}{i}$ .

$n(5,11) = \sum_{i=1}^{5} \binom{11}{i} = \sum_{i=0}^{5} \binom{11}{i} - 1 = \frac{2^{11}}{2} - 1 = 1023$ .

---

One can also notice that $\sum_{m=1}^{p} \binom{m}{n} = \binom{p+1}{n+1}$ .

So induction can be used to get $n(e,p) = \sum_{i=1}^{e} \binom{p}{i}$ , using the base case $n(0,p) = 0$ and using $n(e,p) = [\sum{i=0}^{p-1} n(e-1,i) ] + p$ .

Inductive step: assuming $n(k,p) = \sum_{i=1}^{k} \binom{p}{i}$ for all $p$ , $n(k+1,p) = [\sum_{i=0}^{p-1} n(k,i) ] + p = [\sum_{i=0}^{p-1} \sum_{j=1}^{k} \binom{i}{j} ] + p = [\sum_{j=1}^{k} [\sum_{i=0}^{p-1} \binom{i}{j}] ] + p = [\sum_{j=1}^{k} \binom{p}{j+1}] + \binom{p}{1} = \sum_{j=1}^{k+1} \binom{p}{j}$ .