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
We will go through this problem for the
# Two eggs
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
What could we do differently 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?
Which can be rewritten as:
Or, in closed form as:
This tells us that with
# Three eggs
We have already previously established the best strategy for
Let’s define some terminology:
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
This can be rewritten as:
which results in:
Solving this, we get
Let’s see if we can generalize this for
We can safely say that with
So we can write equation 1 as the following:
We can expand this as the following:
and substitute in equation 1 to get:
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
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
Let’s implement this problem.
We can implement equation 3 as a function:
julia> f(x, n) = x == 0 || n == 0 ? 0 : 1 + f(x - 1, n) + f(x - 1, n - 1) f (generic function with 1 method)
And, we can verify that it works for
We can implement this generally like so:
julia> function starting_floor(floors, n) for x in 1:floors if f(x, n) >= floors return x end end end starting_floor (generic function with 1 method)
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|
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.