There is a 200-storey building. You are given 5 identical glass marbles. You are allowed to drop any marble from any floor to the ground. A marble either breaks or remains intact after a drop. If it remains intact, the marble can be reused.

In the worst case, what is the minimum number of drops needed to find the highest floor in the building from which you can drop the marbles without breaking them?

## Tim Little solved this puzzle:

Let f(d, m) be the number of floors for which this problem can be solved using m marbles and d drops in the worst case.

Obviously, f(1, m) = 1 and f(d, 1) = d.

If you have m marbles, then you can drop the first from floor f(d - 1, m - 1) + 1. If it breaks, you have m - 1 marbles and d - 1 drops to distinguish the floors below. If it does not break, you can distinguish up to f(d - 1, m - 1) floors above. Therefore,

f(d, m) = f(d - 1, m - 1) + f(d - 1, m) + 1

Generating the values of f(d, m) for some values of d and m, we get,

From the table, 8 drops with 5 marbles will suffice for a building with 200 floors (indeed, up to 218 floors), but 7 drops will not.

## Susam Pal from cotpi added:

Here is a more elaborate but less elegant way to solve it. Let f(d, m) be the maximum number of floors in the building out of which the highest floor from which the marbles do not break can be figured with m marbles and d drops.

With m marbles available, it can be dropped first from floor F

_{1}= f(d - 1, m - 1) + 1. If it breaks, the remaining m - 1 marbles and d - 1 drops can be used to find the required floor out of the f(d - 1, m - 1) floors between floor 1 and floor F_{1}- 1, inclusive. However, if the marble does not break, we can reuse the marble and drop it from floor F_{2}= F_{1}+ f(d - 2, m - 1) + 1. If it breaks, the remaining m - 1 marbles and d - 2 drops can be used to find the required floor out of the f(d - 2, m - 1) floors between floor F_{1}+ 1 and floor F_{2}- 1, inclusive. However, if it does not break this time as well, we can reuse it and drop it from floor F_{3}= F_{2}+ f(d - 3, m - 1). In general, the k-th drop of the first marble is made from floor F_{k}= F_{1}+ F_{2}+ … + F_{k - 1}+ f(d - k, m - 1) if the first marble survives the first (k - 1)-th drops from floors F_{1}, F_{2}, …, F_{k - 1}.In one of the worst cases in which the first marble surives all available d drops, the last drop would be made from F

_{d}= F_{1}+ F_{2}+ … + F_{d - 1}+ 1 = f(d - 1, m - 1) + f(d - 2, m - 1) + … + f(1, m - 1) + d. This is the maximum number of floors in the building for which the problem can be solved using m marbles and d drops in the worst case. Also, if only one drop and m marbles are available, this problem can be solved for a building with one floor only. So,f(1, m) = 1

f(d, m) = f(d - 1, m - 1) + f(d - 2, m - 1) + … + f(1, m - 1) + d

Using the principle of mathematical induction, it can be shown that:

f(d, m) = C(d, 1) + C(d, 2) + … + C(d, m) for m ≤ d.

f(d, m) = 2

^{d}- 1 for m ≥ d.For a fixed m, f(d, m) increases as d increases. The values of f(d, 5) where 1 ≤ d ≤ 8 are:

So, we can see that at least 8 drops are required to solve this problem for a building with more than 119 floors but less than 219 floors.