The egg drop problem where the aim is to minimise the time taken

283 Views Asked by At

In the standard egg drop problem you are in front of a 100-storey building and by dropping eggs from $k$ different floors you plan to find the lowest floor from which you can drop an egg without breaking it. Your task is to find the smallest $k$ that will ensure you are successful. The answer is 14, or if we replace 100 with $n$ it is $ \left\lceil \sqrt{2n} - \frac{1}{2} \right\rceil$.

Let us now change the problem so that it takes 1 minute to travel up or down a storey. Nothing else takes any time. You start outside the building. Your task is not to minimise $k$ but to minimise $t$, the time you need to allow, measured in minutes.

A further problem is to find a floor-choosing method that will minimise the mean $t$ required.

1

There are 1 best solutions below

3
On BEST ANSWER

Then there is no faster algorithm than just dropping an egg from each floor as you ascend; if you wanted to start from floor $x$, it would take $x$ minutes to reach that floor to begin, in which time you could have tested every floor up to $x$ anyway.

Thus: drop an egg from each floor. The worst case time would be $n$, which would always require at least $n$ minutes to find out simply because you must travel to that floor to distinguish between a solution of $n$ and $n-1$.