%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

Indeed, let $F(b,t)$ be the quantity described in the title
and let $G(b,t):={{t} \choose {b}}+{{t} \choose {b-1}}+ \dots + {{t} \choose {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$. \halmos

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.

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


