\documentclass[11pt,twoside]{article}

%\usepackage{course}% !! use the macros at home
\usepackage{latex-macros/course}% !! use the macros

\newcommand{\rem}{\textup{ rem }}

\begin{document} 
\inclassproblems{12, Wed.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem} Let's extend the reasoning behind the Binomial Thereom to the
case of multinomials.

\bparts

\ppart What is the coefficient of $x^2 y^5 z^3$ in $(x + y + z)^{10}$?

\solution[\vspace{1.5in}]{This is equal to the number of ways to
rearrange the letters in a word with 2 $x$'s, 5 $y$'s, and 3 $z$'s,
which is:

\[
\frac{10!}{2!\ 3!\ 5!}
\]
}

\ppart What is the coefficient of $b o^2 k^2 e^3 p r$ in $(b + o + k +
e + p + r)^{10}$?

\solution[\vspace{0.75in}]{This is equal to the number of ways to
rearrange the letters in the word ``bookkeepper'', which is:

\[
\frac{10!}{1!\ 2!\ 2!\ 3!\ 1!\ 1!}
\]
}

\eparts

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\instatements{\newpage}

\begin{problem}
An {\em error-correcting code} is a collection of dissimilar $n$-bit
sequences, which are called {\em codewords}.  For example, here is an
error-correcting code consisting of 5-bit codewords:

\[
\set{\ 00000,\  11100,\  01111,\  10011\ }
\]

If one of these codewords is transmitted across a wire and a single
bit is flipped in the process, then the receiver can still determine
which codeword was sent.  Now let's consider an error-correcting code
with 7-bit codewords that also tolerates single-bit errors.

\bparts

\ppart How many 7-bit sequences are there?

\solution[\vspace{0.5in}]{$2^7$ by the product rule.}

\ppart Let $B = (b_1, \ldots, b_7)$ be a codeword.  Someone who
receives a 7-bit sequence that differs from $B$ in at most one
position will conclude that $B$ was sent.  How many such sequences are
there?

\solution[\vspace{0.5in}]{Seven codewords differ in one position and
one codeword differs in zero positions, for a total of eight.}

\ppart Based on these answers, give an upper bound on the number of
7-bit codewords in an error-correcting code that tolerates single-bit
errors.

\solution[\vspace{1in}]{For each codeword $B$, there are 8 sequences
that the receiver interprets as $B$.  Therefore, the code can contain
at most:

\begin{eqnarray*}
\left\lfloor\frac{2^7}{8}\right\rfloor & = & 16 \text{ codewords}
\end{eqnarray*}
}

\ppart When I was an undergraduate, someone claimed a theoretical
breakthrough: an error-correcting code with sixteen 8-bit codewords
that tolerated two-bit errors.  Outrageous claims are common in
information theory, but I didn't know enough at the time to refute
this.  Extend the reasoning above to prove this claim false.

\solution[\vspace{2.5in}]{There are $2^8 = 256$ different 8-bit
sequences.  Someone who receives a sequence differing from a codeword
$B = \set{b_1, \ldots, b_2}$ in at most two positions will conclude
that $B$ was sent.  There are:
\[
\binom{8}{0} + \binom{8}{1} + \binom{8}{2} =  1 + 8 + 28 = 37
\]
such sequences.  Therefore, a code with 8-bit codewords and {\em
two-bit} error correction can not have more than:
\[
\floor{\frac{256}{37}}=  6 \text{ codewords}.
\]
}

\ppart \textbf{(challenge)} Construct an error-correcting code with
7-bit codewords that tolerates single-bit errors and has a number of
codewords equal to the upper bound you computed in part (c).

\eparts

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\instatements{\newpage}

\newcommand{\edge}[2]{#1\text{---}#2}

\begin{problem}
We're going to prove that there exists a way to do the magic trick
without magic.  Recall that a bipartite graph looks something like
this:

\bigskip
\centerline{\resizebox{!}{1in}{\includegraphics{bipartite-example}}}
\bigskip

There are some vertices on the left and some vertices on the right.
Every edge connects a left-vertex to a right-vertex.

\bparts

\ppart Let the left-vertices be the {\em sets} of 5 cards that the
audience might select.  How many left-vertices are there?

\solution[\vspace{1in}]{
\[
\binom{52}{5}
\]
}

\ppart Let the right-vertices be the {\em sequences} of 4 distinct
cards that the assistant might reveal.  How many right-vertices are
there?

\solution[\vspace{1in}]{
\[
52 \cdot 51 \cdot 50 \cdot 49
\]
}

\ppart A set of 5 cards (on the left) is joined by an edge to a
sequence of 4 cards (on the right) if and only if the assistant could
reveal that sequence if the audience selects that set.  What is the
degree of each left-vertex?  What is the degree of each right-vertex?

\solution[\newpage]{Each left-vertex has degree $\binom{5}{4}
\cdot 4! = 120$.  Each right vertex has degree 48.}

\ppart Recall that a {\em matching} for the left-vertices is a subset
of edges that joins each left-vertex to exactly one right-vertex.  For
example, a matching is shown below in bold:

\bigskip
\centerline{\resizebox{!}{1in}{\includegraphics{bipartite-example-matched}}}
\bigskip

How is a matching for the left-vertices related to the magic trick?

\solution[\vspace{2in}]{The magician and the assistant agree on a
matching in advance.  The audience selects a set of 5 cards.  The
assistant reveals the matched sequence of 4 cards.  From the matching,
the magician now knows that corresponding set of 5 cards.  He names
the one which he has not already seen.}

\ppart Recall Hall's theorem:

\begin{theorem*}
A matching for a set of girls with a set of boys can be found if and
only if every subset of girls likes at least as large a set of boys.
\end{theorem*}

Prove that the bipartite graph constructed above has a matching for
the left-vertices.

\solution{Let $S$ be a set of $n$ vertices on the left.  Since each
vertex on the left has degree 120, the total number edges incident to
vertices in $S$ is $n \cdot 120$.  Since each vertex on the right has
degree 48, these edges must be incident to at least $n \cdot 120 / 48
\geq n$ vertices on the right.  Thus, a matching exists by Hall's
Theorem.}

\eparts

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}
