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

The statement of the title is equivalent to:

Prop. Let T_{b}(x) be the minimal number of throws needed to determine the cut-off floor, in an x-floor building, where it is no longer safe to throw down a glass ball without breaking it, if you have b glass balls that you are allowed to break. Then

T_{b}(x) = t , if \binom{t − 1}{b} + \binom{t − 1}{b − 1} + … + \binom{t − 1}{1} < x ≤ \binom{t}{b} + \binom{t}{b − 1} + … + \binom{t}{1} .

Proof: T_{b}(x) obviously satisfies the dynamical-programming recurrence:

T_{b}(x) = {min \atop 1 ≤ i ≤ x} max ( T_{b−1}(i − 1) , T_{b}(x − i) ) ,

but so does the function on the right hand side, as a routine but somewhat tedious verification shows. The proposition follows by induction on b and x, starting with the obvious initial conditions T_{1}(x) = x and T_{b}(0) = 0.

Strategy: Without loss of generality let x = \binom{t}{b} + \binom{t}{b−1} + … + \binom{t}{1} . The first ball has to be thrown from floor number \binom{t−1}{b−1} + \binom{t−1}{b−2} + … + \binom{t−1}{1} + 1. If it breaks use the b − 1 remaining balls and proceed recursively for the floors below it. If it does not break make this floor the ground floor, and use t−1 throws (and the b balls) to tackle the remaining x = \binom{t−1}{b}+\binom{t−1}{b−1}+…+\binom{t−1}{1} floors above it.

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.