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

• I don't understand what you mean by "maximum number of floors you can check"? What number are you trying to compute? (Also, could you edit the question so you're not using $N$ to mean both the number of eggs available and the floor from which an egg is dropped?) – David Richerby Oct 1 '16 at 12:13
• Explain us the riddle as if we didn't already know it. – Yuval Filmus Oct 1 '16 at 14:25
• @DavidRicherby, I did the edit. Thanks. 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. – Smart Home Oct 1 '16 at 16:04

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:
1. 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)$.
2. Since we've already settled the behavior at floor $x$, we need to have $x=f(n-1,d-1)+1$.
3. 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.