2 Eggs and 100 Floors Problem: a Dynamic Programming Approach

Today, I encountered the “two-egg problem,” which — as is explained in this post — goes as follows:

A building has 100 floors. One of the floors is the highest floor an egg can be dropped from without breaking.

If an egg is dropped from above that floor, it will break. If it is dropped from that floor or below, it will be completely undamaged and you can drop the egg again.

Given two eggs, find the highest floor an egg can be dropped from without breaking, with as few drops as possible.

We can assume the eggs break at the same floor and what we’re looking for is the next floor down — our highest-non-breaking-floor (n). We can also assume once an egg is broken, it’s gone forever.

Two-Eggs-Bellman equation

For an x-floor building, let J(x) be the minimum number of drops needed to find the highest floor an egg can be dropped from, assuming the worst case.

If you drop an egg from a y-floor of an (x+1)-floor building, there are two cases:

• the egg doesn’t break, so you know you can solve the same problem now but for a “smaller building”, that is, solving for an (x-y)-floor building using at most J(x-y) drops,
• the egg breaks, so you only have one egg left, and the number of drops needed to know the maximum floor is, at most, (y-1).

So, in the worst case, you know you need a maximum of max(J(x-y), y-1) drops to solve every subproblem. Because you already dropped one egg, we have that

J(x+1) ≤ 1 + max(J(x-y), y-1)

So, minimizing over y, we have that J satisfies

J(x+1) = 1 + min_{1≤y≤x-1} max(J(x-y), y-1)

The above equation is the Bellman equation for this particular problem.

Solving the equation with Python

It is very obvious that J(1) = 1 and J(2) = 2. Therefore, a Python script with an iterative solution for the equation is

N = 100
J = list(range(N+1))
for x in range(3,N+1):
     J[x] = 1 + min([max([y-1,J[x-y]]) for y in range(1,x)])
print(J[N])

We obtained J(100) = 14, which means that the minimum number of drops needed to determine the maximum floor in a 100-story building is 14, in the worst-case scenario.

The magic

Discovering that the “popular” solution for the problem is based on solving the equation x(x + 1)/2 = 100 was very cool because we unintentionally obtained the seemingly useless identity:

J(N) = ⌈Positive solution of x(x + 1)/2 = N⌉

where J is the solution of the Bellman equation, and ⌈⌉ denotes ceiling.

You can use Wolfram to solve the quadratic equation. Here is an example with N = 3000, so that the solution of the Bellman equation is J(N) = 77, and the positive solution of the equation of x(x + 1)/2 = N is ≈76.961: