Solution to Puzzle #94: Two Eggs and a Building

Again an overwhelming response to the puzzle, that I thought was a difficult one. But some of the die hards sent an answer immediately. Only two people gave a fully correct answer – Suman Saraf, whose 10 year old also could do this one with some hints and Karan Sharma (my nephew from Jaipur) – amazing & very well done!

The correct answer is that there is a way to do this in a maximum of 14 trials.

Here is the solution:

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.

Many people tried variations, i.e. you do at try 50th floor first (binary method) and then if it breaks, then you try from 1st onwards until 50 or start 51st onwards if it does not break.

Some others tried alternate floor strategy, i.e. go 2, 4, 6, …and wherever it breaks try n-1.

One of the more intuitive and innovative solutions is to start with sqrt (n), n in this case being 100, so start with 10, 20, 30, ….and wherever it breaks, start with the previous one+1 onwards. This will require a maximum of 19 trials, or ~2 sqrt(n).

However, the best way to do this is the following (taken directly from Gurmeet’s site) – 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.

Hope you all enjoyed the puzzle!

This entry was posted in Solution and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s