2
$\begingroup$

This is a modification of the infamous egg drop problem, which I have seen formulated as in the following manner:

  • Given $e$ eggs and a building of $f$ floors, how can we find the lowest floor at which the egg drops in the minimum number of throws?
  • Given $e$ eggs and $t$ allowed throws, what is the highest floor we can test?

I know people can solve this using dynamic programming; however, is it possible to extend this to a building with infinite floors, but with a finite lowest floor at which the egg breaks? In other words,

  • Given $e$ eggs and an infinitely tall building, is it possible to find the lowest floor at which the egg drops in as few throws as possible, and if so, how?
New contributor
Ice Tea is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
1
  • 9
    $\begingroup$ The question is ill-defined. One needs to say more clearly what "in as few throws as possible" means. In the classical setting (finite number of floors), one asks for a strategy to minimized the maximal number of throws required in all cases. Since there are only finitely many cases, this makes sense. Here, this maximal number will be infinity for any viable algorithm, thus the sentence "in as few throws as possible" has no clear meaning. $\endgroup$
    – WhatsUp
    Oct 14 at 4:56
4
$\begingroup$

Given an unbounded number of trials, we could simply test one egg over and over and over again until it breaks, and find our floor. "But that's too slow", you say, and you're right - so instead we

pick an arbitrary $k$, and test multiples of $k^{e-1}$! Once that egg breaks, we can start at the last safe spot and test larger multiples of $k^{e-2}$, and after the second egg breaks test multiples of $k^{e-3}$...

The only information we need to solidify our method is...

an initial guess for $N$. Given a suitable scale that we can anticipate $N$ to be in, we can attempt a $k$ such that the worst-case time is minimized. But this simply entails cutting down the length of the first set of trials (of length $\frac{N}{k^{e-1}}$) to manageable size, and then shrinking the rounds where the base-$k$ digits of $N$ are searched for, but this simply involves picking the first $k$ such that $N$ (or your upper bound on it) has $e$ digits.

$\endgroup$
3
  • $\begingroup$ The exclamation mark has a specific meaning in math. $\endgroup$ Oct 15 at 20:32
  • $\begingroup$ The exclamation mark isn't math-rendered, so it doesn't mean factorial. $\endgroup$ 2 days ago
  • $\begingroup$ I figured it out quickly enough, but it still had me pause. You are right, but I suggest you reconsider anyway: is distracting the reader something you want? $\endgroup$ yesterday
3
$\begingroup$

Optimizing for number of throws t given a large amount of eggs, starting at throw n = 0 until success at throw t:

1) Test floor $2^n$ until breakage at floor $2^X$.
2) Binary search between $2^{X-1}$ and $2^X$ until break point is found.

This finds the max floor for arbitrarily high floor F in

t = $O(log(F)^2)$ time (and eggs)

$\endgroup$
4
  • $\begingroup$ How does the specific number of eggs available factor in here? $\endgroup$
    – StephenTG
    Oct 13 at 13:53
  • $\begingroup$ You can't really optimize an algorithm for two variables at the same time. Depending on e the algorithm to minimize t will change. So, this definitely isn't a complete answer but I figured I'd pitch in the algorithm for t independent of e first, in case it helps someone. All said, I don't think this question is solvable with a single algorithm. $\endgroup$ Oct 13 at 14:10
  • $\begingroup$ We don't need to optimize for eggs used, but we need to ensure our algorithm doesn't exceed our number of eggs. $\endgroup$
    – StephenTG
    Oct 13 at 14:50
  • $\begingroup$ Since OP specifically states that F isn't "arbitrarily high" but indeed infinite, here F is infinite, log(F) is too, and so is the number of required drops. (The problem lies with the question, not the answer though: selecting the lowest egg-breaking floor from an infinite building doesn't work like it would with any finite building height.) $\endgroup$
    – Bass
    Oct 15 at 7:52
3
$\begingroup$

The best strategy is to

use a single egg, start from floor 1, and then proceed to the next floor up until the egg breaks.

This will take

a countably infinite number of

steps, which is optimal: it breaks the least possible number of eggs, and if you were to use some other strategy to choose the floors,

no matter which floor-choosing strategy you pick, and no matter how many steps it takes, as long as the number of tested floors is finite,
- the highest floor you tested is also finite, and therefore
- exactly 100% of the floors in the building are higher up than that, so
- there's a 100% chance you didn't reach the lowest egg-breaking floor yet

so the expected number of steps won't be any less for that other strategy, either.

This happens because "infinity is really, really big", or more specifically:

Choosing a single "lowest egg-breaking floor" from an infinite number of possibilities with an equal probability distribution is impossible, so until some other probability distribution is specified, the question is a bit broken.

And so is, of course, any answer, including this one :-)

$\endgroup$
2
  • $\begingroup$ This answer seems to duplicate @AxiomaticSystem's earlier answer for $e=1$, but unlike that answer (which will in the limit be a constant factor of $k^{e-1}$ faster) it does not address what happens when $e>1$, nor allow tuning of itself to a given probability distribution (described in that answer as rot13(n fhvgnoyr fpnyr gung jr pna nagvpvcngr $A$ gb or va))... so I've upvoted the earlier and more complete answer. $\endgroup$
    – Steve
    16 hours ago
  • $\begingroup$ @Steve Well, you should of course vote however you please, for whichever reasons you choose, that's how the site is supposed to work. To me it seems that the answer you call "more complete" actually completely ignores OP's question, which is (and I quote): "is it possible to extend this to a building with infinite floors". $\endgroup$
    – Bass
    3 hours ago

Your Answer

Ice Tea is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.