Here is a fun puzzle:

You are given two eggs, and access to a 100-storey tower. Both eggs are identical. The aim is to find out the highest floor from which an egg will not break when dropped out of a window from that floor. If an egg is dropped and does not break, it is undamaged and can be dropped again. However, once an egg is broken, that’s it for that egg.

If an egg breaks when dropped from a floor, then it would also have broken from any floor above that. If an egg survives a fall, then it will survive any fall shorter than that.

The question is: What strategy should you adopt to minimize the number egg drops it takes to find the solution? (And what is the worst case for the number of drops it will take?)

Once you solved it for two eggs, can you solve it for three eggs? Can you find a generalized solution when you have a tower with

floors and if you have eggs?

** Spoiler warning**: If you have not seen this
problem before I urge you to give it a go before continuing further. I’m
going to post the solution to this below, so this is your spoiler
warning.

If you are interested in an easy to understand intuitive explanation
to the

We will go through this problem for the

## # Two eggs

We have

Let’s consider what we would do if we had just one egg.

With just one egg, we could drop the egg from floor

This means that for a tower with *minimum* number of drops to *guarantee* that we find at
which floor the egg would break. Or in other words, we can search *breaking floor*. Here,

What could we do differently with

With

As an example, let’s say you decide to drop the first egg from every

We can do even better though.

Let’s assume that the minimum number of drops required to guarantee
finding the breaking floor for a

When we drop the first egg from floor

If the egg doesn’t break on the second drop, we have now used

Seeing the pattern here?

For a

Which can be rewritten as:

Or, in closed form as:

We know

This tells us that with

## # Three eggs

We have already previously established the best strategy for

Let’s define some terminology:

where

And we know that

So if we have 3 eggs and if the first egg breaks on the first drop,
we want to ensure that we can check

For the second drop, we can start from floor:

For the third drop, we can start from floor:

Seeing a pattern emerge again?

Similar to before, the total number of floors we can check is
constrained by

This can be rewritten as:

which results in:

Solving this, we get

## #
eggs

Let’s see if we can generalize this for

With

where

We can safely say that with

So we can write equation 1 as the following:

For

We can expand this as the following:

and substitute in equation 1 to get:

And, for

Again, we can expand it and rearrange some terms:

and substitute in equation 2 to get:

We can see a pattern emerging here. The generalized equation can be written like so:

This is also known as a recurrence relation.

This result can be reasoned through intuition as well. To find the
total floors you can check with

If we wanted to, we could expand this recurrence relationThanks to /u/possiblywrong for pointing this out [1]..

Here is the expansion increasing the depth in the direction of number of drops:

Eagle eye readers will notice a pattern.

It turns out that this expansion is related to the binomial coefficients.

If we had infinite number of eggs, you’d see that the first element
is the only term that contributes to

Using this, we can say that, with

## # Implementation

Let’s implement this problem.

We can implement equation 3 as a function:

For

And, we can verify that it works for

We can implement this generally like so:

And get the answer to the problem programmatically.

Using the function `f`

, we can also generate a table that
explores what is the maximum number of floors that can be check for
various number of drops and eggs.

1 egg | 2 eggs | 3 eggs | 4 eggs | 5 eggs | 6 eggs | 7 eggs | 8 eggs | 9 eggs | 10 eggs | |
---|---|---|---|---|---|---|---|---|---|---|

1 drop |
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |

2 drops |
2 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |

3 drops |
3 | 6 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 |

4 drops |
4 | 10 | 14 | 15 | 15 | 15 | 15 | 15 | 15 | 15 |

5 drops |
5 | 15 | 25 | 30 | 31 | 31 | 31 | 31 | 31 | 31 |

6 drops |
6 | 21 | 41 | 56 | 62 | 63 | 63 | 63 | 63 | 63 |

7 drops |
7 | 28 | 63 | 98 | 119 | 126 | 127 | 127 | 127 | 127 |

8 drops |
8 | 36 | 92 | 162 | 218 | 246 | 254 | 255 | 255 | 255 |

9 drops |
9 | 45 | 129 | 255 | 381 | 465 | 501 | 510 | 511 | 511 |

10 drops |
10 | 55 | 175 | 385 | 637 | 847 | 967 | 1012 | 1022 | 1023 |

11 drops |
11 | 66 | 231 | 561 | 1023 | 1485 | 1815 | 1980 | 2035 | 2046 |

12 drops |
12 | 78 | 298 | 793 | 1585 | 2509 | 3301 | 3796 | 4016 | 4082 |

13 drops |
13 | 91 | 377 | 1092 | 2379 | 4095 | 5811 | 7098 | 7813 | 8099 |

14 drops |
14 | 105 | 469 | 1470 | 3472 | 6475 | 9907 | 12910 | 14912 | 15913 |

15 drops |
15 | 120 | 575 | 1940 | 4943 | 9948 | 16383 | 22818 | 27823 | 30826 |

You’ll notice that the upper right corner of the table stays the same if you increase the number of eggs you have at your disposal. You can see this even more clearly in this visualization.

There’s a minimal number of drops required to guarantee that you will find the breaking floor, even if you have unlimited eggs.

If you want to check

For 100 floors, it is

Partitioning the floors equally or in other words bisecting the floors, and exploring the partition of interest using the same strategy is the most efficient way of finding the breaking floor.

So there you go! We have solved the general case for the egg and tower puzzle.