The Maximal number of floors a Building can have where you can tell the highest floor

from where you can throw a glass ball without breaking it, if you have b glass balls and are allowed t throws is \binom{t}{b} + \binom{t}{b−1} + … + \binom{t}{1}

By Shalosh B. EKHAD

Indeed, let F (b, t) be the quantity described in the title and let G(b, t) := \binom{t}{b} + \binom{t}{b−1} + … + \binom{t}{1}. After the first throw, if the ball broke, the maximal number of floors that you can handle below it is F (b − 1, t − 1), and if it didn’t break, the maximum floors that you can handle above it is F (b, t − 1), so we have the recurrence F (b, t) = F (b − 1, t − 1) + F (b, t − 1) + 1 with the initial condition F (1, t) = t. By the Pascal-Chu-defining recurrence for the binomial coefficients, G(b, t) = G(b − 1, t − 1) + G(b, t − 1) + 1. Since G(1, t) = t, the statement follows by induction on b and t.

The strategy is clear. Throw a ball from floor G(b − 1, t − 1) + 1. If it breaks explore (recursively) the G(b−1, t−1) floors below, (with the remaining b−1 balls and t−1 throws). Otherwise, explore (recursively) the G(b, t − 1) floors above.

Acknowledgement: This apparently ancient puzzle was brought to my attention by Nati Linial, via my master, Doron Zeilberger.

First version: Nov. 7, 2010. This version: Nov. 10, 2010.