1
$\begingroup$

I have a question about the binomial coefficient solution to the generalization of the egg dropping problem (n eggs, k floors)

enter image description here In the binomial coefficient solution we construct a function $f(x,n)$, which represents the maximum number of floors we can cover with $x$ trials and $n$ eggs.

So there are two cases, if we drop an egg. Either it breaks, so we have $x-1$ trials left and $n-1$ eggs, or it does not break, so we have $x-1$ trials left and $n$ eggs.

Thus we have the following recursive expression: $$ f(x,n)=1+f(x-1,n)+f(x-1,n-1) $$

I cannot understand why we are adding the terms $f(x-1,n)$ and $f(x-1,n-1)$. As only one of the two contingencies happens, (the first egg breaks or not), why do we use simultaneously both terms in the sum.

Can someone please explain that in detail?

Thank you in advance

$\endgroup$
  • 1
    $\begingroup$ The thing is that if the egg breaks, then you only have to cover the lower floors, as you know that it will break for all the higher floors. And if the egg doesn't break, you only have to cover the higher floors. So the floors that would get covered by $f(x-1,n)$ automatically get covered when the egg brakes, and those that would get covered by $f(x-1,n-1)$ automatically get covered when the egg doesn't brake. In both cases you can thus sum these terms. $\endgroup$ – Tassle Dec 9 '19 at 17:33

Your Answer

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

Browse other questions tagged or ask your own question.