Vtgyjfy

In the egg drop problem, you have two eggs and you want to determine from which floors in a $n$ - floor building you can drop an egg such that is doesn't break. You are to determine the minimum number of attempts you need in order to find the critical floor in the worst case while using the best strategy.

Some assumptions :

• If the egg doesn't break at a certain floor, it will not break at any
  floor below.


• If the eggs breaks at a certain floor, it will break at any floor
  above.


• The egg may break at the first floor.


• The egg may not break at the last floor.

This problem is popular and there are many ways to solve it. I am wondering how to solve it with the following twist : instead of minimizing the worst case, how would one minimize the average case ? We consider that the egg has equal probability $1/n$ to break on a given floor (and above).

An attempt :

Let $f(2,n)$ denote the minimum number of drops needed to cover $n$ floors with the $2$ eggs.
For the worst case, the following recursive equation holds

$$
f(2,n) = 1 + min_{1 le x le n} bigl{ max{f(1,x-1),f(2,n-x } bigr }
$$

Roughly speaking, when throwing the first egg from a given floor $x$, there are two scenarios :

1. If the egg breaks, we are left with $1$ egg and have to check the $x-1$ floors below


2. If the egg does not break, the $n-x$ floors above $x$ have to be checked with the $2$ eggs

Since the number of trials in worst case is minimized, we take the maximum of these two cases for every floor and choose the floor which yields minimum number of drops. The extra $1$ accounts for the drop before knowing if the egg broke or not. The base cases are trivially $f(1,0)=f(2,0)=0$ (no drops needed if there are no floors), $f(1,1)= f(2,1) = 1$ (one drop is sufficient if there is only one floor), and $f(1,x) = x$ ($x$ drops needed if only one egg is available - each floor must be tested one by one).

For the average case, I believe the recursive equation becomes

$$
f(2,n) = 1 + min_{1 le x le n} bigl{ p(x)f(1,x-1)+(1-p(x))f(2,n-x) bigr },
$$
where $p(x)$ is the probability that the egg breaks on floor $x$, i.e., the probability that $x$ is above the critical floor. If this critical floor is represented by a discrete random variable $Y$ with uniform distribution on $[1,n]$ :
$$
p(x) = P(xge Y)
$$

I am not sure if this correct. And if so, how can this expression be simplified?

Also, the base cases remain $f(1,0)=f(2,0)=0$, $f(1,1)=f(2,1)=1$, but $f(1,x)$ no longer equals $x$, since we are interested in the average case.

Any help is welcome, any other approach is welcome. Thanks.

Since an egg may break at the first floor, the critical floor may be the zero floor so I assume that the probability that the critical floor is $k$-th floor equals $frac 1{n+1}$ for each $k=0,dots, n$. Remark that $f(1,0)$ means that an egg dropped from the zeroth floor doesn’t break.

When there remains only one egg then since we have to find the critical floor and any floor has a non-zero probability to be critical, we still must test each floor one by one. Remark that either if a critical floor is last or previous to last, anyway we need to drop the egg from all floors. Thus $f(1,n)$ is the expected number of attempts which is equal to

$$sum_{k=0}^{n-1} frac 1{n+1}{k+1}+nfrac 1{n+1}=frac 1{n+1}left(frac{n(n+1)}{2}+nright)=frac n2+1-frac{1}{n+1}.$$

Now the recursive equation is

$$ f(2,n) = 1 + min_{1 le x le n} left{frac{x}{n+1}f(1,x-1)+ frac{n+1-x}{n+1}f(2,n-x) right}=$$ $$1+ frac 1{n+1}min_{1 le x le n} left{frac{x(x+1)}2-1 + (n+1-x)f(2,n-x) right}.$$

Or, substituting $g(n)=(n+1)f(2,n)$, we have $g(0)=0$, $g(1)=2$, and

$$g(n)=n+1+ min_{1 le x le n} left{frac{x(x+1)}2-1 + g(n-x)right}.$$

I wrote a program to calculate the sequence ${g(n)}$ for $nle 15000$. It turned out that a sequence ${g(n)-g(n-1)}$ has a simple pattern:

2, 3, 3, 4, 4, 4, 5, 5, 5, 5,...

This suggests that $g(n)=g(n-1)+leftlfloorfrac {sqrt{8n-7}+3}2rightrfloor$, and

$$frac{6-4sqrt{2}}{6}n^{1/2}le g(n)-frac{4sqrt{2}}6n^{3/2}-nle frac{sqrt{2}}{6}n^{1/2}.$$

Below is the graph of a function $$left(g(n)-frac{2sqrt{2}}3n^{3/2}-nright)n^{-1/2}$$