0

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 Answers1

1

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

Phil H
  • 1,338
  • Thanks. So this wasn't such a good question after all. I will try to craft another where one has to minimise some function of the amount of walking about inside the building and the number of eggs. –  Aug 15 '18 at 13:30
  • You could modify it to introduce some nonlinearity or to model the problem better. The original problem addresses the issue of finding which element of an array is the first to fail a predicate via the fewest evaluations of that predicate. The assumption is that values are cheap to access, and that the predicate is expensive to evaluate. Your question changed that to address the problem where the cost is linear in the traversal distance. An alternative (and gnarlier) version might be if evaluations were to be done in batches of $m$, and each batch had a constant cost; i.e. cache friendliness – Phil H Aug 16 '18 at 09:09
  • Unfortunately I don't understand most of that. What if dropping an egg and learning whether or not it has broken takes time? Perhaps an increasing amount as time goes on? So 1 minute for the first egg, 2 for the second, etc.? –  Aug 16 '18 at 14:26