0
$\begingroup$

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

Solution:

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.

$\endgroup$
  • 2
    $\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 '19 at 14:19
  • 1
    $\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 '19 at 17:57
  • 3
    $\begingroup$ Which among these questions and answers about egg dropping could be a precedence of this question? $\endgroup$ – John L. Jan 24 '19 at 19:27
  • 4
    $\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 '19 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 '19 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.