Dissecting the Famous Egg Dropping Puzzle

Google’s interview question just got a whole lot simpler.

Egg dropping puzzle (2-egg, 100-floor version).

“Figure out the highest floor of a 100-floor building an egg can be dropped without breaking, given two eggs”

The Egg Dropping Puzzle is a mathematical puzzle that has been around the internet for some time now, which is known to be adopted in interviews of major companies like Google, Microsoft, Accenture and even Hewlett Packard.

You are to determine the minimum number of attempts required in the worst case to find the critical floor.

Photo by Pablo Vargas via Unsplash

Assumptions in the egg dropping puzzle:

1. The two eggs are identical.
2. If an egg does not break by dropping from a certain floor, it will not break dropping from any floor below that.
3. If an egg breaks by dropping on a certain floor, it will break dropping from any floor above that.
4. An egg may break by dropping on the 1st floor.
5. An egg may not break by dropping even on the 100th floor.

Note:

• If you don’t want it to get spoiled, you’d want to stop reading from here and start working out the answer.
• If you have already read and known the solution, you can skip the following and go ahead to read the combinatorial view of the solution.

Solution to the 2-egg, 100-floor egg dropping puzzle.

While the answer is not too hard to understand, it takes some twists of one’s thought to arrive at the answer.

The solution is derived using the utilization of a restricted number of trials. And then the 2-egg, n-floor solution can be easily generalized.

A step-by-step solution to optimize the answer:

• If the first egg breaks, we need to test the remaining floors one by one starting from the lowest until the remaining egg breaks. For example, if the first drop is on the 50th floor and the egg breaks, it will take 49 more drops from the 1st floor to the 49th floor to ensure the remaining egg does not break until we know the answer.
• If the first drop is on the 10th floor and it breaks, then it takes a total of 10 trials to know the answer in a worst case scenario, i.e. the egg starts to break on the 9th or the 10th floor. The trials will be: 10 → 1 → 2 → 3 → 4 → 5 → 6 → 7→ 8 → 9
• To utilize the number of trials used (10 trials), if the first drop is on the 10th floor and the egg does not break, the second drop should be on the 19th floor, i.e. if the egg breaks on the 19th floor, then you should drop the eggs in the following sequence: 10 → 19 → 11 → 12 → 13 → 14 → 15 → 16 → 17 → 18 (10 trials in total).
• With this utilization in mind, the ultimate sequence (if an egg never breaks) will be 10 → 19 (10 + 9) → 27 (10 + 9 + 8) → 34 (10 + 9 + 8 + 7) → 40 → 45 → 49 → 52 → 54 → 55, i.e. 10 trials can test up to 55 floors.
• Using the formula for triangle numbers, m trials can test for [m(m+1)]/2 floors, i.e.

13 trials can test 13 * 14 / 2 = 91 floors14 trials can test 14 * 15 / 2 = 105 floors

Thus it takes 14 trials to test a 100-floor building.

Let’s view the solution in combinatorics.

To derive the general solution of the egg dropping puzzle with any number of eggs, let’s review the 2-egg case again. We will interpret the solution in an alternative way.

To keep things simple, we are going to work with 15 floors only. We will drop the eggs (IF an egg does not break) on floors 5, 9, 12, 14, 15, which implies that a maximum of 5 trials is sufficient to obtain the answer. The table below shows all the possible outcomes.

Remarks:

• An egg is broken in trials highlighted in yellow.
• The “Answer” refers to the highest floor known not to break an egg.

There are in total 16 cases, corresponding to the answers 0 to 15 for the 15-story building. By analyzing the distribution of the trials that break the egg, i.e. the yellow cells, we can see that the 16 cases are indeed divided into 3 groups:

0 yellow cells: 1 case (rows in orange)

1 yellow cell: 5 cases (rows in green)

2 yellow cells: 10 cases (rows in cyan)

To utilize all the trials and the eggs, the number of cases should be the same as the number of total possible combinations of the yellow cells, i.e.

Therefore the 15-floor building can be represented by:

And we can generalize the solution for 2 eggs given m trials:

Maximum number of floors that can be tested will be…

Now how about egg dropping puzzle with 3 eggs?

As usual, we will start with a simple case: 3 eggs with 4 trials.

• If the first trial breaks the (first) egg, there will be 2 remaining eggs with 3 trials, which, according to the above, can test 6 floors. This means we should drop the first egg from the 7th floor.
• If it breaks by dropping from the 7th floor, we will follow the strategy for testing a 6-floor building with 2 eggs in 3 trials, i.e. throwing out from floor: 3, 5 and 6 (if the eggs do not break).
• If an egg does not break by dropping from the 7th floor, we can repeat the rationale above to determine the next floor we should drop an egg. If the next drop breaks the egg, there will be 2 remaining eggs with 2 trials, which can test 3 floors. It means that the second trial will be on the 11th floor, leaving floor: 8, 9, 10 for the 2 remaining trials with 2 eggs (if an egg breaks by dropping from the 11th floor).

Following the same strategy, if an egg does not break on the 11th floor, we will try floor 13, and then 14 if an egg does not break on the 13th floor.

A picture is worth a thousand words (or so they say):

The combinatorial view can be applied here too! The reason is that the optimal strategy should utilize all the possible trials with the given number of eggs, where every different egg-breaking combination (a total of 15 combinations in this case) should produce a different answer.

To express this numerically, it will be:

Remarks:

• An egg is broken in trials highlighted in yellow.
• The “Answer” refers to the highest floor known not to break an egg.

The general solution with x eggs and m trials.

Based on the above discussion, the general solution will be:

With x eggs and m trials, the maximum number of floors of a building we can test is given by:

Considering the possible case where x > m, we should write the general solution as:

A quick question for the readers: what is the implication when x > m?

An extract of the numerical values of the general solution is shown below. The answer for the initial problem with 2 eggs and a 100-floor building is highlighted, i.e. 100 is bound by 91 and 105 hence the answer is 14 trials.

A full spreadsheet with these numerical values and a number-of-trial calculator is available.

For those of you who want to explore even further…

1. For programmers, write a program to obtain the number of trials needed for testing on an n-story building given x eggs. (Need hint? https://en.wikipedia.org/wiki/Dynamic_programming#Egg_dropping_puzzle)
2. Why can the trials utilize all the possible combinations?
3. Given x eggs with m trials, which floor will you drop the egg on the kth trial (given that no eggs will break even on the highest floor)?

Originally published at code.oursky.com on July 18, 2016. Any comments? Share with us below!

😻 At Oursky we’re all about helping brands and entrepreneurs make their ideas happen. Get in touch if you’re looking for a partner to help build your next digital product.