-1
$\begingroup$

Venus gave you two eggs because she wants to test their strength.

She lives in a 100 floor building and she wants to find the first floor above which the eggs break when thrown out of the window.

More formally, there exist exactly one so-called critical floor such that: - if you climb up to the critical floor or to any floor above it and then you throw an egg out of the window: the egg will break. - if you climb up to any floor below the critical floor and then you throw an egg out of the window: the egg will not break. In this case you can reach the ground floor, pick up the egg and use it again.

The critical floor is the same for the two eggs; the eggs do not get weaker as you throw them outside.

You have to develop a strategy that find the critical floor using the smallest number of throws in its worst-case scenario.

What does "number of throws in the worst-case scenario" means: Your strategy will likely take a different number of throws depending on which is the critical floor, but it has to work for every possible situation.

Take for example this simple strategy: go to the first floor and throw an egg. If it does not break, go to the second floor and throw it outside again.

Repeating this procedure by climbing up a floor at a time allows you to find the critical floor when the first egg breaks. This strategy uses only a throw if the critical floor is the first one, it takes two throws if the critical floor is the second one and so on.

The worst-case scenario for this strategy is when the critical floor is the last one. In this case you are able to solve the problem using 100 throws: every strategy has a worst-case scenario in which the number of throws used to find the critical floor is maximum.

Your goal is to find a strategy that uses a very small number of throws even in its worst-case scenario.

Source: My professor during a lecture Similar question in which the number of throws are limited: Dinosaur egg drop

$\endgroup$
  • 1
    $\begingroup$ @oray the question is similar, but I do not impose a maximum number of trials, so the answer is a bit different. $\endgroup$ – melfnt Dec 9 '19 at 13:51
  • 2
    $\begingroup$ But it's exactly the same problem, and the trial constraint is meaningless since the goal is to minimize the trials in the worst case scenario. $\endgroup$ – Thomas Markov Dec 9 '19 at 13:52
  • $\begingroup$ No, if I had 20 trials I would throw the first egg from floor 20. If it does not break, I would throw it from 40. $\endgroup$ – melfnt Dec 9 '19 at 13:58
  • 1
    $\begingroup$ The strategy you describe for 20 trials fails to meet the 20 trial max in many cases. $\endgroup$ – Thomas Markov Dec 9 '19 at 14:05
  • 1
    $\begingroup$ The optimal solution is on the linked question here: puzzling.stackexchange.com/a/5011/60730 $\endgroup$ – Thomas Markov Dec 10 '19 at 0:51
3
$\begingroup$

Drop the first egg from

50th floor. if it breaks , start from first floor and try up to 49th floor Number of throws on its worst-case scenario 49+1 = 50 if it doesn't breaks when throw form 50th floor , start from 51 floor and try up to 100th floor Number of throws on its worst-case scenario 50+1 = 51 So Number of throws on in the worst-case scenario of this technique is 51

$\endgroup$
  • $\begingroup$ That's better than 100, but still a lot. See the answers to linked question for a solution that uses only 20 throws, the best solution uses less than 20. $\endgroup$ – melfnt Dec 9 '19 at 22:29
  • $\begingroup$ but we have only 2 eggs. so if one break, we cant risk the other. $\endgroup$ – Sangeetha Dec 10 '19 at 9:29
  • $\begingroup$ Se the answers for the linked question please $\endgroup$ – melfnt Dec 10 '19 at 10:07

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