\problemdata      
        {counting-6} % latex-friendly label for the prob.
        {Counting, Pigeonhole} % The topic(s) of the problem content.
        {F01 Q3} % Source (if known)
        {S02 CP8W; F01 Q3} % 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?

\solution{
If the trick is possible with a deck of $n$ cards, then $n$ must
satisfy 
\[
\text{for all }k\leq n:\quad 
\binom{k}{5} \le (k)_4.
\]
In particular, $\binom{n}{5}\leq (n)_4$ should be true, which holds
iff 
\begin{align*}
\frac{n!}{(n-5)!5!} &\le n(n-1)(n-2)(n-3), 
&&\text{iff}
\\
\frac{n(n-1)(n-2)(n-3)(n-4)}{5!} &\le n(n-1)(n-2)(n-3),
&&\text{iff}
\\
\frac{(n-4)}{5!} &\le 1,
&&\text{iff}
\\
n &\le 124.
\end{align*}
So, any deck that allows the trick has at most $124$ cards. 

Moreover, a 124~card deck allows the trick, since for all $k\leq 124$
we know 
$$
\binom{k}{5} \le (k)_4,
$$
by the equivalence already proven above. 

So, 124 is the largest deck size for which the trick is possible.
}
\end{problem}
