Generalised Two-Egg Puzzle

From Wiki Egg Dropping puzzle we know that the the state transfer equation is:

W(n,k) = 1 + min{ max(W(n − 1, x − 1), W(n,k − x)) } , x = 1, 2, ..., k

W(n,1)=1, W(1,k)=k

n = number of test eggs available

k = number of (consecutive) floors yet to be tested

Below is my understanding.

We have k floors, n eggs, assume we use an egg to test in x floor. there are only two possible results:

1. it breaks, so the problem recursively come to: x-1 floors, n-1 eggs, which reflects to W(n-1,x-1)
2. it doesn't break, so the problem recursively come to: k-x floors, n eggs, which reflects to W(n,k-x)

Since the problem requires the worst case, we have to choose the bigger one to ensure the worst case works, that's why we add an max between W(n-1,x-1) and W(n,k-x).

Besides, as we just assumed testing in x floor, x can be from 1 to k, in this situation, we definitely need to choose the minimum to ensure the min experimental drops to find out N, that's why we add an min between {max(W(n − 1, x − 1), W(n,k − x)): x = 1, 2, ..., k}

Finally, as we have used 1 drop in x floor, so the equation must add 1, which reflects to the first part of the equation.

Hope that solves your puzzle :-)

(1) Consider the case that the first drop breaks the egg. Then you can determine the breakfloor if and only if it is at most f[d-1, e-1]. Therefore you can't start higher than f[d-1, e-1] + 1 (and shouldn't start lower, of course).

(2) If your first drop doesn't breaks the egg, you are in the case of f[d-1, e], just starting at the floor of your first drop + 1, instead of floor 1.

So, the best you can do is to start dropping eggs at floor f[d-1, e-1] + 1 (because of (1)), and you can get up to f[d-1, e] floors higher than that (because of (2)). That's

f[d, e] = f[d-1, e-1] + 1 + f[d-1, e]