Algorithm to find maximum number of floors you can check with N eggs and D maximum drops

Question: You are given access to a multistory building. You have N eggs and are allowed D maximum drops from their window.

Rules: If a egg is dropped from window of floor F and it breaks, it will break for all floors > F.

If an egg is dropped from window of floor F and survives, it will survive for all floors < F.

What is the maximum number of floors you can check in the worst-case?

E.g: With 1 egg and 5 drops, you can check at most 5 floors (1, 2, 3, 4, 5)

With 2 eggs and 5 drops, you can check at most 9 floors (2, 4, 6 ,8, 9)

EDIT: By "maximum floors you can check", I mean the highest floor for which you can guarantee that you know the outcome for all floors <= to it. For. e.g in N = 1, D = 5 case, there is no algorithm that guarantees you will know the outcome at every floor <= 6 in the worst case. This is because in the worst-case: drops from 6, 5, 4, 3, 2 break and you don't know what will happen at floor 1 since you have no more drops left.

My solution is as follows

findMaxFloors(N,D)
{
 nextFloor = 0

 while (D > 0)
 {
    nextFloor += MIN(N, D);
    D = D-1;
 }

 return nextFloor;
}

But the solution given on the forum is more complicated (using recursion)
maxFloors(N+1,D) = maxFloors(N, D-1) + 1 + maxFloors(N+1, D-1)

I would appreciate any suggestions on the conditions under which my solution won't work.

First we'll clarify the problem a bit. We have $n$ eggs, which we can drop from any floor we want. We also have the constraint that we are allowed a total of $d$ drops of these eggs (rather than $d$ drops per egg). Obviously, when we drop an egg and it breaks, we can't drop it again. Let $f(n,d)$ be the maximum number $M$ such that with $n$ eggs and $d$ drops, we can completely describe the behavior of our experiment for floors $1,\dotsc,M$.

In other words, with $M=5$ the possible outcomes are [YYYYY] (the eggs break when dropped from all 5 floors), [NYYYY] (the egg survives a drop from floor 1 but no higher floor), and [NNYYY], [NNNYY], [NNNNy], and [NNNNN]. Obviously, in all possible descriptions, all the N's must come before all the possible Y's

With that out of the way, let's tackle the recursion
$$
f(n,d)=f(n-1,d-1)+1+f(n,d-1)
$$
Our plan of attack is to drop the first egg from floor $x$, yet to be determined.
That egg either breaks or doesn't:

• If it breaks, we know it will break when dropped from any higher floor as well, so we're left with $n-1$ eggs and $d-1$ more drops. In other words, we're looking at the lower floors and there will be $f(n-1,d-1)$ of them, namely floors $1, 2,\dotsc, f(n-1,d-1)$.

• Since we've already settled the behavior at floor $x$, we need to have $x=f(n-1,d-1)+1$.

• If it doesn't break, we know it won't break when dropped from a lower floor, so we still have $n$ eggs and $d-1$ drops remaining, which will mean that we can determine the behavior of the higher $f(n,d-1)$ floors. They will start at floor $x+1$ and will cover floors $x+1, \dotsc, x+f(n,d-1)=f(n-1,d-1)+1+f(n,d-1)$, exactly as the recursion stated.

For example, you correctly observed that $f(1,5)=5$ but your value for $f(2,5)$ was low. In fact, $f(2, d)=d(d+1)/2$, which is 15 in the case where $d=5$. Start with the first drop from floor 5, and you'll see that you can indeed determine the egg behavior at all of the first 15 floors.

StackExchange Computer Science Q#64093, answer score: 7