%glassballs.tex:
%%a Plain TeX file by Shalosh B. Ehhad  (1 page)

%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
  0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
  height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\parindent=0pt
\overfullrule=0in
\def\Tilde{\char126\relax}
\def\frac#1#2{{#1 \over #2}}
%end macros
\bf
\centerline
{
The Maximal number of floors a Building can have where you can tell the highest floor
}
\centerline
{
from where you can throw a glass ball without breaking it, 
}
\centerline
{if you have b glass balls and are allowed t throws is}
\centerline
{
${{t} \choose {b}}+{{t} \choose {b-1}}+ \dots + {{t} \choose {1}}$
}
\rm
\bigskip
\centerline
{By {\it Shalosh B. EKHAD}}
\bigskip

The statement of the title is equivalent to:

{\bf 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 \quad , \quad
if \quad {{t-1} \choose {b}}+{{t-1} \choose {b-1}}+ \dots + {{t-1} \choose {1}}
< x \leq {{t} \choose {b}}+{{t} \choose {b-1}}+ \dots + {{t} \choose {1}} \quad .
$$

{\bf Proof}: $T_b(x)$ obviously satisfies the {\bf dynamical-programming} recurrence:
$$
T_b(x)= {{\min} \atop  {1 \leq i \leq x}}  \quad max \, ( \, \, T_{b-1}(i-1) \, , \, T_b(x-i) \, ) \quad ,
$$
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$.  \halmos

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

{\bf 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.

\end


