Egg drop problem

A very broad hint for version 4: consider that in your version-3 answer you don't have to use uniform intervals between drops of the first egg. Can you see how to use a non-uniform distribution so that the worst-case total is identical no matter where the first egg breaks?


(Version 5: 2 eggs and ≤ 2*sqrt(2)*sqrt(T) tosses)

Drop eggs from floors, 1, 3, 6, 10, 15 and so on.. (3 = 1 + 2, 6 = 1+ 2 + 3, 10 = 1 + 2 + 3 + 4 etc.

Let us say the first egg breaks at floor 21 (that's 1 + 2 + 3 + 4 + 5 + 6). This tells us that T is between 15 and 21. Till now, we have had 6 tosses.

Now, 1 + 2 + 3 +.....t = t(t+1)/2 which can be approximated to t^2/2 for ease of calculation of t is large. So, the floors at which we have been tossing eggs actually are approx. t^2/2 where t is the number of tosses so far.

So, let us come back to the example above for clarity. Here t = 6 and t(t+1)/2 (without any approx.) = 21. So, till now we have had t tries. Now, the next step is to keep tossing eggs sequentially from 16 to 21 till the 2nd egg breaks and we find T out.

The worst case scenario for T is 21 as in that case we'll have to keep breaking eggs till we reach 21. Or, we could generalize and say that the worst case scenario for T is t(t+1)/2 (approx. t^2/2) where t tries have been completed. So t = approx. sqrt(2)*sqrt(T).

Total number of tosses required in reaching floor 21 (assuming that's T in the worst case) will be tosses to reach floor 21 (6) + tosses from 16 to 21 (6 again).

Basically, the total number of tosses required in reaching floor T will be t - to reach the upper bound of T (21 in this case) PLUS sequential tries from the floor before t(t+1)/2th floor.

Now t th toss' floor is t(t+1)/2 t-1 th toss' floor is t(t-1)/2 (that's what 1 + 2 + 3 +.... (t-1) is).

The difference between the two turns out to be t (that means t(t+1)/2 - t(t-1)/2 is t).

So, the maximum number of sequential tries from t(t-1)/2 th floor to t(t+1)/2 th floor is t.

Hence, the final maximum number of tosses in reaching floor T = tosses in reaching floor t(t+1)/2 + sequential tries from t(t-1)/2 th floor to t(t+1)/2 th floor.

So, maximum tosses required = t + t = 2t.

But t = sqrt(2)*sqrt(T).

So, 2t = 2*sqrt(2)*sqrt(T) = maximum tosses required to reach floor T.


For the fifth, take intervals $1,2,3,\cdots$ and then it iterate through the unknown elements. This achieves the desired bound since solving $$\frac{n(n+1)}2=T\implies n\le\sqrt{2T}$$ Yields that the first egg will be thrown at most $\sqrt{2T}$ times. Being the last interval $\sqrt{2T}$, the second egg will be thrown(at most) the same number of times.