computer science – Throwing $K$ glass balls from tower – quadratic recurrence


Super famous related question: We have two identical glass balls, and a tower with 100 floors. We want to find the minimum floor from which the balls will break when dropped, in a minimal number of test throws.

Solution: Suppose we have $n$ throws to work with. What’s the maximum amount of floors we can cover with $n$ throws safely?

Suppose we throw the first ball from floor $n+1$ and it broke. Now we need to cover $n$ floors with $n-1$ throws of a single ball. That’s impossible, so instead we must throw the first ball from at most floor $n$ and it’s clear we should do that. In the best case, it doesn’t break (and so we checked the first $n$ floors) and now we need to throw from floor $n + (n-1)$, and so on.

So the maximum amount of floors we can check with $2$ balls is $n+(n-1)+(n-2) + dots + 1 = frac{n(n+1)}{2}$, we want this to be minimal as possible but greater than $100$, and the answer is $n=14$.

What would happen if we have $K$ balls?

The above solution hints at the direction, I believe. Denote $T(j)$ to be the maximum amount of floors we can cover safely with $j$ balls and $n$ throws. $T(1) = n$ obviously, we already saw $T(2) = frac{n(n+1)}{2}$.

Now I want to know $T(K)$. Going by the above logic, I can’t throw the first ball from floor $T(K-1) + 1$. Again I need to throw from $T(K-1)$, and then $T(K-1) + (T(K-1) – 1)$ and so on, and so

$T(K) = frac{1}{2}T^2(K-1) + frac{1}{2}T(K)$

This is a quadratic recurrence relation. How do we solve such beasts?