Gurmeet.Net
Gurmeet.Net
Puzzles
Puzzles

Two Eggs and a Building

Puzzle

With two eggs and a building with 100 floors, what is the optimal strategy for finding the lowest floor at which an egg will break when dropped? Followup: What if the number of floors of the building is unknown?

Source

Heard from a Googler in 2005.

Solution

(Thanks to Mike who posted this solution as a comment at Puzzles Page)

At any point, if you are left with only 1 egg, the only strategy that will give you the answer is to start at the lowest unknown floor and work your way up one-by-one until the egg breaks or until you reach the top floor.

With 2 eggs, you can improve your strategy by starting somewhere between the lowest unknown floor and the highest unknown floor. If the egg breaks, you can eliminate all upper floors, but then you have to revert to the 1 egg strategy. If the egg doesn't break, you can eliminate that floor plus all floors below it, and then choose another starting point among the remaining floors and repeat.

With 100 floors, you can find the correct floor in 14 drops or less by starting at floor 14. If the egg breaks, you then go to floor 1, work your way up, and will find the correct floor with at most 14 drops. If the egg doesn't break, then move up 13 floors to 27. Again, if it breaks, you work your way up from 15 and will find the correct floor in at most 14 drops. If it didn't, you move up 12 floors, then 11, etc. Using this method, you can see that you will always find the correct floor in 14 or fewer drops.

If you attempt to find the floor with 13 or fewer drops, you can see that you must start at the 13th floor or lower, and after the first drop you can move at most 12 floors, then 11, etc. You will not reach the top of the building within 13 drops, so you cannot guarantee you will find the correct floor.

Therefore, any strategy will in worst case require at least 14 drops.

Followup

For an extensive discussion of this problem, see the article The Egg Game by William Gasarch and Stuart Fletcher, Sep 2008.

Previous Puzzle: Poisoned Wine Barrels

An enemy spy has poisoned one out of 1000 barrels of wine in a king's cellar. Even a sip of the poisoned wine has potency to kill. However, the effects of the poison show only in 30 days. The king asks the royal jailor to identify the poisoned barrel within 30 days. What is the least number of prisoners the jailor must employ to identify the poisoned barrel?

Shankar chooses a number between 1 and 10,000. Geeta has to guess the chosen number as quickly as possible. Shankar will let Geeta know whether her guess is smaller than, larger than or equal to the number. The caveat is that Geeta loses the game if her guess is larger than Shankar's chosen number two or more times. (A) How many guesses are necessary? (B) What if Shankar is allowed to pick an arbitrarily large positive number?

27 Oct 2010
© Copyright 2008—2017, Gurmeet Manku.