\documentclass[11pt,twoside]{article}
\usepackage{latex-macros/course}

\renewcommand{\coursecopyrightnames}
{\href{http://theory.lcs.mit.edu/~meyer}{Prof.~Albert~R.~Meyer}}
%\renewcommand{\coursecopyrightyear}{2003}

\begin{document}
\lecturenotes{9}{The Magic Trick}

There is a Magician and an Assistant.  The Assistant goes into the
audience with a deck of 52 cards while the Magician looks away.  Five
audience members are asked to select one card each from the deck.  The
Assistant then gathers up the five cards and announces four of them to
the Magician.  The Magician thinks for a time and then correctly names
the secret, fifth card!

\section{The Secret}

The Assistant has somehow communicated the secret card to the Magician
just by naming the other four cards.  In particular, the Assistant has
two ways to communicate.  First, he can announce the four cards in any
order.  The number of orderings of four cards is $4! = 24$, so this
alone is insufficient to identify which of the remaining 48 cards is
the secret one.  Second, the Assistant can choose which four of the
five cards to reveal.  The amount of information that can be conveyed
this way is harder to pin down.  The Assistant has $\binom{5}{4} = 5$
ways to choose the four cards revealed, but the Magician can not
determine which of these five possibilities the Assistant selected,
since he does not know the secret card!  Nevertheless, these two forms
of communication allow the Assistant to covertly reveal the secret
card to the Magician.

Here is an overview of how the trick works.  The secret card has the
same suit as the first card announced.  Furthermore, the value of the
secret card is offset from the value of the first card announced by
between 1 and 6.  See Figure~\ref{fig:cardcycle}.  This offset is
communicated by the order of the last three cards.

\begin{figure}[htbp]
\centerline{\includegraphics[height=2.5in]{figures/cardcycle}}
\caption{\em The 13 possible card values can be ordered in a cycle.  For
any two distinct values, one is offset between 1 and 6 clockwise steps
from the other.  In this diagram, $3$ is offset five steps from $J$.
In the card trick, the value of the secret card is offset between 1
and 6 steps from the first card announced.  This offset is
communicated by the order of the last three cards named by the
Assistant.}
\label{fig:cardcycle}
\end{figure}

Here are the details.  The audience selects five cards and there are
only 4 suits in the deck.  Therefore, by the Pigeonhole Principle, the
Assistant can always pick out two cards with the same suit.  One of
these will become the secret card, and the other will be the first
card that he announces.

Here is how he decides which is which.  Note that for any two card
numbers, one is at most six clockwise steps away from the other in
Figure~\ref{fig:cardcycle}.  For example, if the card numbers are $2$
and $Q$, then $2$ is three clockwise steps away from $Q$.  The
Assistant ensures that the value of the secret card is offset between
1 and 6 clockwise steps from the first card he announces.

The offset is communicated by the order that the Assistant announces
the last three cards.  The Magician and Assistant agree in advance on
an order for all 52 cards.  For example, they might use:
\[
A \ \clubsuit, 2 \ \clubsuit, \dots, K \ \clubsuit, A \ \diamondsuit,
\dots, K \ \diamondsuit, A \ \heartsuit, \dots, K \ \heartsuit, A \
\spadesuit, \dots, K \ \spadesuit,
\]
though any other order will do as well---so long as the Magician and his
Assistant use the same one \texttt{:-)}.
With this order, one of the last three cards announced is the
smallest ($S$), one is largest ($L$), and the other is medium ($M$).
The offset is encoded by the order of these three:
\[
\begin{array}{ccc}
SML = 1 & SLM = 2 & MSL = 3 \\
MLS = 4 & LSM = 5 & LMS = 6
\end{array}
\]
For example, suppose that the audience selects $3 \heartsuit \ 8
\diamondsuit \ A \spadesuit \ J \heartsuit \ 6 \diamondsuit$.  The
Assistant picks out two cards with the same suit, say $3 \heartsuit$
and $J \heartsuit$.  The $3 \heartsuit$ is five clockwise steps from
$J \heartsuit$ in Figure~\ref{fig:cardcycle}.  So the Assistant makes
$3 \heartsuit$ the secret card, announces $J \heartsuit$ first, and
then encodes the number 5 by the order in which he announces the last
three cards: $A \spadesuit \ 6 \diamondsuit \ 8 \diamondsuit = LSM =
5$.

\subsection{Same Trick with 4 Cards?}

Could the same magic trick work with just 4 cards?  That is, if the
audience picks four cards, and the Assistant reveals three, then can
the Magician determine the fourth card?  The answer turns out to be
``no''.  The proof relies on the Pigeonhole Principle.

\begin{theorem}
The magic trick is not possible with 4 cards.
\end{theorem}

\begin{proof}
The audience can select any 4-combination of cards; let $A$ be the set
of all such 4-combinations.  The Assistant can announce any
3-permutation of cards; let $B$ be the set of all such 3-permutations.
The formulas for $r$-combinations and $r$-permutations give the
following sizes for $A$ and $B$:

\begin{eqnarray*}
\card{A} & = & C(n, r) \\
    & = & \frac{52!}{48! \ 4!} \\
    & = & 270,725 \\
\card{B} & = & P(n, r) \\
    & = & \frac{52!}{49!} \\
    & = & 132,600
\end{eqnarray*}

The Assistant sees a 4-combination of cards selected by the audience and
must announce a 3-permutation to the Magician.  Let $f: A \mapsto B$ be
the function that the Assistant uses in mapping one to the other.  Since
$\card{A} > \card{B}$, the Pigeonhole Principle implies that $f$ maps at
least two 4-combinations to the same 3-permutation.  That is, there are
two different sets of four cards that the audience can pick for which the
Assistant says exactly the same thing to the Magician.

For these two sets of four cards, three cards must be the same (since
the Assistant announces the same three cards in both cases) and one
card must be different (since the two sets are different).  For
example, these might be the two sets of four cards for which the
Assistant says exactly the same thing to the Magician:

\begin{eqnarray*}
3 \heartsuit \ 8 \diamondsuit \ A \spadesuit \ J \heartsuit \\
3 \heartsuit \ 8 \diamondsuit \ A \spadesuit \ K \diamondsuit
\end{eqnarray*}

In this case, the Assistant announces $3 \heartsuit \ 8 \diamondsuit \
A \spadesuit$ in some order.  The magician is now stuck; he can not
determine whether the remaining card is $J \heartsuit$ or $K
\diamondsuit$.
\end{proof}

There are many variants of the magic trick.  For example, if the
audience picks 8 cards, then revealing 6 to the Magician is enough to
let him determine the other two.  This sort of subtle transmission of
information is important in the security business where one wants to
prevent information from leaking out in undetected ways.
\end{document}
