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?

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,

                               m
        ---------------------------------------------------
        |  1    2    3    4    5    6    7    8    9   10 |
    -------------------------------------------------------
    | 1 |  1    1    1    1    1    1    1    1    1    1 |
    | 2 |  2    3    3    3    3    3    3    3    3    3 |
    | 3 |  3    6    7    7    7    7    7    7    7    7 |
    | 4 |  4   10   14   15   15   15   15   15   15   15 |
  d | 5 |  5   15   25   30   31   31   31   31   31   31 |
    | 6 |  6   21   41   56   62   63   63   63   63   63 |
    | 7 |  7   28   63   98  119  126  127  127  127  127 |
    | 8 |  8   36   92  162  218  246  254  255  255  255 |
    | 9 |  9   45  129  255  381  465  501  510  511  511 |
    |10 | 10   55  175  385  637  847  967 1012 1022 1023 |
    -------------------------------------------------------

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.

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₁ = 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, inclusive. However, if the marble does not break, we can reuse the marble and drop it from floor F₂ = F₁ + 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 and floor F₂ - 1, inclusive. However, if it does not break this time as well, we can reuse it and drop it from floor F₃ = F₂ + f(d - 3, m - 1). In general, the k-th drop of the first marble is made from floor F_k = F₁ + F₂ + … + F_{k - 1} + f(d - k, m - 1) if the first marble survives the first (k - 1)-th drops from floors F₁, F₂, …, 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₁ + F₂ + … + 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:

• f(1, 5) = 1
• f(2, 5) = 3
• f(3, 5) = 7
• f(4, 5) = 15
• f(5, 5) = 31
• f(6, 5) = 62
• f(7, 5) = 119
• f(8, 5) = 218

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.