Egg drop. Suppose that you have an $n$-story building (with floors 1 through $n$) and plenty of eggs. An egg breaks if it is dropped from floor $T$ or higher, and does not break otherwise. Your goal is to devise a strategy to determine the value of $T$ given the following limitations on the number of eggs and tosses:

  • Version 3: 2 eggs and $\sim 2 \sqrt{n}$ tosses.
  • Version 4: 2 eggs and $\sim c\sqrt{T}$ tosses for some fixed constant $c$.


Version 3: find an interval of size $\sqrt{n}$, then do sequential search. Note: can be improved to $\sim \sqrt{2n}$ tosses.

Version 4: $1 + 2 + 3 + \dots + t \sim \frac{1}{2}t^2$. Aim for $c = 2\sqrt{2}$.

Can someone explain to me versions 3 & 4? And let me know of any resources to go about learning this.

I'm doing Princeton university's algorithm part 2 on Coursera.

  • 1
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – Discrete lizard Jan 24 at 14:19
  • $\begingroup$ Version 3 is the famous egg dropping puzzle. You can find many online resources. Version 4 is very similar. $\endgroup$ – Yuval Filmus Jan 24 at 17:57
  • 3
    $\begingroup$ Which among these questions and answers about egg dropping could be a precedence of this question? $\endgroup$ – Apass.Jack Jan 24 at 19:27
  • 3
    $\begingroup$ You have a large portion of your question in a quote section, which makes me guess it is copied from somewhere. Please credit the original source of all copied material, as per our guidelines (cs.stackexchange.com/help/referencing). $\endgroup$ – D.W. Jan 24 at 19:36
  • $\begingroup$ actually I do not understand the question of 2 eggs and ~ 2√n tosses limitation. I think it means that I've only 2 eggs to throw. but what about the 2√n tosses limitation ? $\endgroup$ – DarkArtistry Jan 25 at 1:52

Your Answer

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

Browse other questions tagged or ask your own question.