Dissecting Famous Egg Dropping Puzzle

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 scenario to find the critical floor.

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 for 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, -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, trials can test for floors, i.e.
  • 13 trials can test 13 * 14 / 2 = 91 floors
  • 14 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-storey 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 trials:

Maximum number of floors that can be tested will be

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:

Illustration for 3 eggs with 4 trials, testing for a maximum of 14 floors

1. Trial 1 is on floor 7
2. Floor to try goes downward/upward if the egg does/doesn't break
3. Trial 4 positions are not shown because they are trivial

                     +--------------+
             +->     | 14           |
             |       +--------------+
       +->  Trial 3  | 13           |
       |     |       +--------------+
       |     +->     | 12           |
                     +--------------+
 +->  Trial 2        | 11           |
 |                   +--------------+        Note 2
 |     |     +->     | 10           |   <--+
 |     |     |       +--------------+      | 2 eggs with 2 trials can
 |     +->  Trial 3  |  9           |      | test for 3 floors when
 |           |       +--------------+      | the first egg breaks on floor 11
 |           +->     |  8           |   <--+ in the 2nd trial
                     +--------------+
Trial 1              |  7           |
                     +--------------+
 |           +->     |  6           |   <--+
 |           |       +--------------+      |
 |     +->  Trial 3  |  5           |      | Note 1
 |     |     |       +--------------+      |
 |     |     +->     |  4           |      | 2 eggs with 3 trials can
 |                   +--------------+      | test for 6 floors when
 +->  Trial 2        |  3           |      | the first egg breaks on floor 7
                     +--------------+      | in the 1st trial
       |     +->     |  2           |      |
       |     |       +--------------+      |
       +->  Trial 3  |  1           |   <--+
                     +--------------+

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 eggs and trials, the maximum number of floors of a building we can test is given by:

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

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

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.

no. of trials () \ no. of eggs ()	1	2	3	4	5	6
1	1	1	1	1	1	1
2	2	3	3	3	3	3
3	3	6	7	7	7	7
4	4	10	14	15	15	15
5	5	15	25	30	31	31
6	6	21	41	56	62	63
7	7	28	63	98	119	126
8	8	36	92	162	218	246
9	9	45	129	255	381	465
10	10	55	175	385	637	847
11	11	66	231	561	1,023	1,485
12	12	78	298	793	1,585	2,509
13	13	91	377	1,092	2,379	4,095
14	14	105	469	1,470	3,472	6,475
15	15	120	575	1,940	4,943	9,948

Explore Further

1. For programmers, write a program to obtain the number of trials needed for testing on an -storey building given 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 eggs with trials, which floor will you drop the egg on the th trial (given that no eggs will break even on the highest floor)?

Tell us what you think and subscribe to our blog if you find this helpful.

Follow us on twitter to get updated.