\problemdata      
        {?} % latex-friendly label for the prob.
        {Counting} % The topic(s) of the problem content.
        {?} % Source (if known)
        {Fall 2001, quiz 3} % Usage (list ones you are aware of).
        {Christos Kapoutsis, S02} % Last revision info (author, date).


\begin{problem}
We know how the ``Magic'' trick works in which an Assistant reads
four cards from a five card hand and the Magician predicts the fifth card.
We also know the trick cannot be made to work if the Assistant only
shows three cards from a four card hand, because there are fewer sequences
of three out of 52 cards than there are 4-card hands out of 52 cards.

A basic result in matching theory called \emph{Hall's Theorem} implies
that, in general, the trick is possible using $h$-card hands chosen from
an $n$-card deck, with the Assistant reading $r$ of the $h$ cards as long
as the following condition holds:
\begin{quotation}\noindent
for \emph{every subset} of the $n$ cards in the deck, the number of
$h$-card \emph{hands} from that subset is at most as large as the number
of $r$-card \emph{sequences} from that subset.
\end{quotation}
Given Hall's Theorem (which is not at all obvious by the way),
what is the largest size deck for which our trick of reading four cards
from a 5-card hand remains possible?

\brule{1in}

\solution{Need
\[
\binom{k}{5} \le (k)_4
\]
for all $k \le n$.  That is,
\begin{eqnarray*}
\frac{k!}{(k-5)!5!} &\le& k(k-1)(k-2)(k-3)\\
\frac{k(k-1)(k-2)(k-3)(k-4)}{5!} &\le& k(k-1)(k-2)(k-3)\\
\frac{(k-4)}{5!} &\le& 1\\
k &\le& 124.
\end{eqnarray*}
So $n = 124$ is the largest size deck for which the trick is possible.
}

\end{problem}