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

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query
\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

\begin{document} 
\inclassproblems{10, Mon.}                    % !! start the paper


% Follow up to INCLASS MAGIC TRICK DEMO
% source: F02 cp9W which was taken from F99 tut16 & S99 tut9


\begin{problem}
A bipartite graph is {\em regular} if every vertex on the left has the
same degree, $c$, and every vertex on the right has the same degree, $d$.

\bparts

\ppart\label{cd} Prove the following:
\begin{corollary*}
A regular bipartite graph has a matching for the vertices on the left
iff $c \geq d > 0$.
\end{corollary*}

\hint Consider the set of edges between any set, $L$, on the left and its
set of neighbors, $N(L)$, on the right.

\solution{We first show that if $c \geq d > 0$, then for every set of
vertices, $L$, on the left
\begin{equation}\label{cL}
\card{L} \leq N(L).
\end{equation}
Hall's Theorem will then imply that there is a matching.

To prove~\eqref{cL}, let $F$ be the set of edges incident to some set $L$
on the left.  Now $\card{F}$ is the sum of the degrees of the vertices of
$L$, so
\[
\card{F} = c \card{L}.
\]
On the other hand, $F$ is a subset of the edges incident to $N(L)$, so
\[
\card{F} \leq d \card{N(L)}.
\]
Hence,
\[
c \cdot \card{L} \leq d \cdot \card{N(L)},
\]
and so
\[
\card{L} \leq \frac{d}{c} \cdot \card{N(L)} \leq \card{N(L)}
\]
since $d/c \leq 1$.  This proves~\eqref{cL}.

Conversely, suppose $c < d$.  Consider the previous argument where $L$ is
the set of \emph{all} left vertices.  Now the set of edges incident to $N(L)$
actually is the same as the edges incident to $L$, so
\[
c \cdot \card{L} = d \cdot \card{N(L)},
\]
and therefore
\[
\card{L} = \frac{d}{c} \cdot \card{N(L)} > \card{N(L)}.
\]
So $L$ violates the condition of Hall's Theorem necessary for a matching,
and no matching is possible.}

\ppart Conclude that the Magician could pull off the Card Trick with a
deck of 124 cards.

\solution{
By the first part, the Magician can determine the 5th card as long as the
degree of each hand is at most the degree of each sequence of 4.  Whatever
the size of deck, the degree of each hand is $5! = 120$.  The degree of
each sequence of 4 will be the number of cards remaining in the deck.
With a deck of 124, there will be 120 cards remaining, so the degree of
each sequence of 4 will still be $leq$ the degree of each hand.

Note that by part~\eqref{cd}, the trick could not be done with any deck
larger than 124.
}

\eparts

\end{problem}


\begin{problem} We have just demonstrated how to determine the 5th
card in a poker hand when a collaborator reveals the other 4 cards.
Describe a similar method for determining 2 hidden cards in a hand of 9
cards when your collaborator reveals the other 7 cards.

\solution{
Since there must be $\ceil{9/4} = 3$ cards with the same suit, our
collaborator chooses to hide two of them and then use the third one as the
first card to be revealed.  So this first revealed card fixes the suit of
the two hidden cards; it will also be used as the origin for the offset
position of the first hidden card.  This first hidden card will in turn be
used as the origin for the offset of the other hidden card.  There are six
cards to code the two offset positions.  These suffice to code two offsets
of size from one to six.  That is, our collaborator can choose one of the
$3! = 6$ orders in which to reveal the first three cards and thereby tell
us the offset position of the first hidden card.  Our collaborator can
then choose the order of the final three cards to describe the offset
position of the second hidden card from the first.  Note that the first
revealed card must be chosen so that both offsets are less $\leq 6$; since
the sum of the offsets between successive cards ordered in a cycle from Ace
to King is 13, it is not possible for more than one offset between
successive cards to exceed seven, so this is always possible.
}

\end{problem}

\instatements{\newpage}

\begin{problem} The Tao of BOOKKEEPER: we seek enlightenment through
contemplation of the word $BOOKKEEPER$.

\bparts

\ppart In how many ways can you arrange the letters in the word
$POKE$?

\solution{There are $4!$ arrangments corresponding to
the $4!$ permutations of the set $\set{P, O, K, E}$.}

\ppart In how many ways can you arrange the letters in the word
$BO_1O_2K$?  Observe that we have subscripted the O's to make them
distinct symbols.

\solution{There are $4!$ arrangments corresponding to
the $4!$ permutations of the set $\set{B, O_1, O_2, K}$.}

\ppart Suppose we map arrangements of the letters in $BO_1O_2K$ to
arrangements of the letters in $BOOK$ by erasing the subscripts.
Indicate with arrows how the arrangements on the left are mapped to
the arrangements on the right.

\[
\begin{array}{lcl}
\begin{array}{l}
O_2BO_1K \\
KO_2BO_1 \\
O_1BO_2K \\
KO_1BO_2 \\
BO_1O_2K \\
BO_2O_1K \\
\ldots
\end{array}
& \hspace{2in} &
\begin{array}{l}
BOOK \\
OBOK \\
KOBO \\
\ldots
\end{array}
\end{array}
\]

\ppart What kind of mapping is this, young grasshopper?

\solution{2-to-1}

\ppart In light of the Division Rule, how many arrangements are there
of $BOOK$?

\solution{$4! / 2$}

\ppart Very good, young master!  How many arrangements are there of
the letters in $KE_1E_2PE_3R$?

\solution{$6!$}

\ppart Suppose we map each arrangement of $KE_1E_2PE_3R$ to an
arrangement of $KEEPER$ by erasing subscripts.  List all the different
arrangements of $KE_1E_2PE_3R$ that are mapped to $REPEEK$ in this way.

\solution{$RE_1PE_2E_3K$, $RE_1PE_3E_2K$,
$RE_2PE_1E_3K$, $RE_2PE_3E_1K$, $RE_3PE_1E_2K$, $RE_3PE_2E_1K$}

\ppart What kind of mapping is this?

\solution{3!-to-1}

\ppart So how many arrangements are there of the letters in $KEEPER$?

\solution{$6! / 3!$}

\ppart {\em Now you are ready to face the BOOKKEEPER!}

How many arrangements of $BO_1O_2K_1K_2E_1E_2PE_3R$ are there?

\solution{$10!$}

\ppart How many arrangements of $BOOK_1K_2E_1E_2PE_3R$ are there?

\solution{$10! / 2!$}

\ppart How many arrangements of $BOOKKE_1E_2PE_3R$ are there?

\solution{$10! / (2! \cdot 2!)$}

\ppart How many arrangements of $BOOKKEEPER$ are there?

\solution{$10! / (2! \cdot 2! \cdot 3!)$}

\ppart How many arrangements of $VOODOODOLL$ are there?

\solution{$10! / (2! \cdot 2! \cdot 5!)$}

\ppart \textbf{(IMPORTANT) } How many $n$-bit sequences contain $k$
zeros and $(n-k)$ ones?

\solution{$\binom{n}{k}$}
\eparts

\vspace{0.3in}

\begin{center}
\textit{Remember well what you have learned: subscripts on, subscripts off.}

\textit{This is the Tao of Bookkeeper.}
\end{center}

\end{problem}

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

\instatements{\newpage}

\begin{problem}
Solve the following counting problems.  Define an appropriate mapping
(bijective or $k$-to-1) between a set whose size you know and the set
in question.

\bparts 

\ppart How many different ways are there to select a dozen donuts if
four varieties are available?

\solution{There is a bijection from selections of a
dozen donuts to 15-bit sequences with exactly 3 ones.  In particular,
suppose that the varieties are glazed, chocolate, lemon, and Boston
creme.  Then a selection of $g$ glazed, $c$ chocolate, $l$ lemon, and
$b$ Boston creme maps to the sequence:
%
\[
(g\ 0's)\ 1\ (c\ 0's)\ 1\ (l\ 0's)\ 1\ (b\ 0's)
\]
%
Therefore, the number of selections is equal to the number of 15-bit
sequences with exactly 3 ones, which is:
%
\[
\frac{15!}{3!\ 12!} = \binom{15}{3}
\]
}

\ppart How many paths are there from $(0, 0)$ to $(10, 20)$ consisting
of right-steps (which increment the first coordinate) and up-steps
(which increment the second coordinate)?

\solution{There is a bijection from 30-bit sequences with 10 zeros and 20
ones.  The sequence $(b_1, \ldots, b_{30})$ maps to a path where the
$i$-th step is right if $b_i = 0$ and up if $b_i = 1$.  Therefore, the
number of paths is equal to $\binom{30}{10}$.}

\ppart An independent living group is hosting nine new candidates for
membership.  Each candidate must be assigned a task: 1 must wash pots, 2
must clean the kitchen, 3 must clean the bathrooms, 1 must clean the
common area, and 2 must serve dinner.  In how many ways this be done?

\solution{There is a bijection from sequences containing one
$P$'s, two $K$'s, three $B$'s, a $C$, and two $D$'s.  In any such
sequence, the letter in the $i$th position specifies the task assigned to
the $i$th candidate.  Therefore, the number of
possible assignments is:
\[
\frac{8!}{1!\ 2!\ 3!\ 1!\ 2!}
\]
}

\ppart In how many ways can Mr. and Mrs. Grumperson distribute 13
identical pieces of coal to their two--- no, three!--- children for
Christmas?

\solution{There is a bijection from 15-bit strings
with two ones.  In particular, the bit string $0^a10^b10^c$ maps to
the assignment of $a$ coals to the first child, $b$ coals to the
second, and $c$ coals to the third.  Therefore, there are
$\binom{15}{2}$ assignments.}

\ppart How many solutions over the natural numbers are there to the
equation:

\begin{eqnarray*}
x_1 + x_2 + \ldots + x_{10} & \leq & 100
\end{eqnarray*}

\solution{There is a bijection from 110-bit sequences
with 10 ones to solutions to this equation.  In particular, $x_i$ is
the number of zeros before the $i$-th one but after the $(i-1)$-st one
(or the beginning of the sequence).  Therefore, there are
$\binom{110}{10}$ solutions.}

\ppart (Quiz 2, Fall '03) Suppose that two identical 52-card decks are
mixed together.  In how many ways can the cards in this double-size deck
be arranged?

\solution{The number of sequences of the 104 cards containing 2 of each
card is $104! / (2!)^{52}$.}

\eparts

\end{problem}

\end{document}
