Loading…

A logical task about the height of an egg crash

You are given a 100-story building. If the egg is dropped from the Nth floor height (or from a greater height), it will break. If you drop it from any smaller floor, it will not break. You have two eggs. Find the N value using the minimum number of shots.

 

We want to pay your attention that it does not matter what floor we throw egg №1 off. The matter is when we throw an egg №2, we need to use a linear search (from the lowest to the highest floor) between the crash floor and the next highest floor when throwing an egg will escape unhurt. For instance, if egg №1 escapes unhurt when falling from the 5th to the 10th floor, but it is broken when throwing from the 15th floor, then you will need to throw the egg №2 (in the worst case) off the 11th, 12th, 13th and 14th floors.

 

Let’s suppose we throw an egg off the 10th floor, and then off the 20th floor.

 

  • If egg №1 was broken during the first throw (floor 10th), then we need to do no more than 10 throws (in the worst case).

  • If egg №1 is broken during the last throw (100th floor), then we have 19 throws ahead in the worst case (floors 10th, 20th, …, 90th, 100th, then from 91st to 99th).

 

We have discussed those two cases, but let’s now take a look at the worst case. Let’s do load balancing to highlight the two most likely situations.

 

  1. In a well-balanced system, the value of Throws (Egg1) + Throws (Egg2) will be constant, no matter on which floor the egg №1 was broken.

  2. Let’s suppose egg №1 makes one step (floor) during each throw, and egg №2 moves one less step.

  3. Each time it is necessary to reduce by 1 the number of shots that are potentially necessary for egg №2. In case egg №1 is thrown first off the 20th floor and then off the 30th floor, then egg №2 will need no more than 9 throws. When we throw egg №1 again, we must reduce the number of throws of egg №2 to 8. In order to make it, throw egg №1 from the 39th floor.

  4. We know that egg №1 should start from floor X, then descend to X-1 floors, then to X-2 floors, until the number 100 is reached.

  5. We can create the formula that describes our solution: X + (X – 1) + (X – 2) + … + 1 = 100 -> X = 14.

 

This way, we first reach the 14th floor, then the 27th, then the 39th. Thus, the 14 steps are the worst case.


Leave a Comment