0

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

melfnt
  • 5,132
  • 2
  • 13
  • 58
  • 1
    @oray the question is similar, but I do not impose a maximum number of trials, so the answer is a bit different. – melfnt Dec 09 '19 at 13:51
  • 2
    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. – Thomas Markov Dec 09 '19 at 13:52
  • 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. – melfnt Dec 09 '19 at 13:58
  • This will solve the problem even if it does not minimise the total number of throws – melfnt Dec 09 '19 at 13:59
  • 1
    The strategy you describe for 20 trials fails to meet the 20 trial max in many cases. – Thomas Markov Dec 09 '19 at 14:05
  • Sorry, I meant 39 (=20+19) and so on. The point is that a strategy that uses exactly 20 throws will solve the linked question but it will my solve mine. In other words: there is a solution takes less than 20 throws – melfnt Dec 09 '19 at 14:23
  • 1
    The optimal solution is on the linked question here: https://puzzling.stackexchange.com/a/5011/60730 – Thomas Markov Dec 10 '19 at 00:51

1 Answers1

3

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

Sangeetha
  • 161
  • 2