# 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?