I have a question about the binomial coefficient solution to the generalization of the egg dropping problem (n eggs, k floors)
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
Best Answer
Suppose that with $x$ trials and $n$ eggs, we can cover $y$ floors, and we drop the first egg from floor $z$.
From the above, we choose $y$ and $z$ so that $z = f(x-1,n-1)+1$ and $y -z = f(x-1,n)$. This lets us cover exactly $$ y = (y-z) + z = f(x-1,n) + f(x-1,n-1) + 1 $$ floors.