This riddle first appeared in print in "Which Way Did the Bicycle Go?", a collection of 191 problems. 

When approaching the riddle, the first thing is to try and figure out the framework in which it can be solved. Basically, the egg drop riddle is a search, so we try and figure out which search algorithm would be best suited. Most people try the first and most popular algorithm that comes to mind, the so-called binary search, or ‘how to catch a lion in the desert’.

The basic idea is to divide the search area in half at every step. So, for the egg drop riddle we would start by dividing the 100 floors into two halves, throw the egg from the 50th floor and see what happens. If the egg breaks, we would know that the critical floor is between 0 and 49, if it doesn’t, the critical floor is between 50 and 100. The algorithm then says, take the set of 50 floors that we continue with, divide them in two and check again. This is fine if the egg doesn’t break, but if it does, we are stuck because we only have one egg left and have to check each and every floor from the bottom up. This kind of binary search is called a balanced binary search because it doesn’t distinguish between two uneven cases - whether the egg breaks or not (this can be depicted graphically using a balanced binary search tree).

We only have two eggs and if the egg breaks at the 50th floor, we might need to use up 49 more throws to be certain to find the critical floor, so the balanced binary search doesn’t really helps us. The solution is to use a non-balanced binary search algorithm - the computer science term for the algorithm used in the solution. This search takes into account the asymmetrical nature of the riddle - the fact that if the first egg breaks we have no choice but to check the remaining set of floors ‘bottom up’, but if it doesn’t we can continue the process of reducing the size of the set of floors we have left to check.

A thorough, formal analysis of the egg dropping riddle within the framework of search trees and dynamic programming can be found in Moshe Sniedovitch’s excellent article.

Although the solution to the riddle has its roots in search algorithms, there is also a connection to other topics in math such as number theory. Note that the solution to the problem can be given by solving the inequality: ½ ✕ n ✕ (n-1) ≥ 100, for n where n is the number of throws. Interestingly, the left-hand side of the inequality is the formula for a triangular number. This is hardly surprising though, since the solution reduces the number of floors in the search set by 1 in every step. We can, however, use this information to easily find the number of throws needed for a building of any height. It is just the serial number of the corresponding triangular number. Here is a list of the first fifteen triangular numbers: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120. We can immediately deduce that for a building one floor high we will need 1 throw, for a 2 to 3 floor building we will need 2 throws, for a building 4-6 floors high we will need 3 throws.

If you want to dig even deeper into this riddle, try it with more than two test eggs and a building with a different number of floors.

Next Section »