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

%\hidesolutions         
%\showsolutions
\renewcommand{\coursecopyrightnames}{Dr.~Radhika~Nagpal and Prof.~Charles~E.~Leiserson}

\begin{document}
\inclassproblems{9, Wed}

% Follow up to INCLASS MAGIC TRICK DEMO
% source: from F99 tut16 & S99 tut9
\begin{problem} We have just demonstrated how to ``guess'' the 5th
card in a poker hand when a collaborator reveals the other 4 cards.
Describe a method for guessing 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 cars 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.
}

% \problempart Show that there is no procedure for ``guessing'' a hidden card
% among four when your collaborator reveals three. \hint Compare the number
% of hands to the number of revealed three-card sequences.
% ~
% \solution{
% There are $\binom{52}{4}$ possible four-card hands.  There are $P(52,3)$
% three-card sequences that can ever be revealed.  Since
% \[
% \frac{\binom{52}{4}}{P(52,3)}=
% \frac{52\cdot 51\cdot 50 \cdot 49/4!}{52 \cdot 51 \cdot 50} = 49/24 > 1,
% \]
% there must, by pigeonholing, be two (actually three) hands for which the
% collaborator reveals the same three cards.  Therefore the magician cannot
% determine the hidden card, since these hands must have different hidden
% cards.}
\end{problem}

% source: Q3 Fall01
% topics: pigeon hole, perms and combs
\begin{problem}

\ 

\begin{problemparts}

\problempart\label{a} Prove the following corollary to Hall's Marriage Theorem.
\begin{corollary}
Let $G=(V_1,V_2,E)$ be a bipartite graph where
$\card{V_1}\leq\card{V_2}$.  Suppose that a positive integer $k$
exists such that each node in $V_1$ is adjacent to at least $k$
vertices in $V_2$ and each node in $V_2$ is adjacent to at most $k$
vertices in~$V_1$.  Then, $G$ contains a perfect matching on the
vertices in~$V_1$.
\end{corollary}

\solution{
\begin{proof}
For any set, $S$ of nodes, let $\text{N}(S)$ be the nodes that are
adjacent to some node in $S$, and let $\text{E}(S)$ be the set of edges
incident on some node in $S$.  That is
\begin{eqnarray*}
\text{N}(S) & \eqdef & \set{u \suchthat \exists s \in S\ (u,s) \in E}\\
\text{E}(S) &\eqdef & \set{(u,s) \suchthat u \in V_1 \union V_2 \text{ and } s \in S}.
\end{eqnarray*}
(Remember that the graph is undirected, so $(u,v)$ and $(v,u)$ describe
the same edge.)

Consider any subset $S\subseteq V_1$.  Since $G$ is bipartite,
$\text{N}(S)\subseteq V_2$.  Since every edge incident to a node in $S$
is by definition also incident to a node in $\text{N}(S)$, we have
$\text{E}(S) \subseteq \text{E}(\text{N}(S))$ so
\[
\card{\text{E}(S)} \le \card{\text{E}(\text{N}(S))}.
\]

Since each node in $V_1$ has at least $k$ incident edges, we have
\[
k\cdot\card{S} \leq \card{\text{E}(S)}.
\] 
Likewise, since each node in $V_2$ has at most $k$ incident edges,
\[
\card{\text{E}(\text{N}(S))} \le k\cdot\card{\text{N}(S)}.
\]
Combining these inequalities yields
\[
k\cdot \card{S} \le \card{\text{N}(S)} \le \card{\text{E}(\text{N}(S))} \le
k \cdot \card{\text{N}(S)}.
\]
Since $k>0$, we conclude that
\[
\card{S} \le \card{\text{N}(S)},
\]
and by Hall's Marriage Theorem, the graph contains a perfect matching on
the vertices in~$V_1$.
\end{proof}
}

\problempart Use part~(\ref{a}) to determine the largest-size
deck for which the trick of reading 4 cards from a 5-card hand remains
possible.  (You must not only determine an upper bound, you must prove
the bound is achievable.)

\solution{
If the trick is possible with a deck of $n$ cards, then $n$ must
satisfy 
\[
\binom{n}{5} \le P(n,4)
\]
where $n\geq 5$, since we must have at least 5 cards in the deck.
That is, 
\[
\frac{n!}{(n-5)!5!} \leq  n(n-1)(n-2)(n-3)  = \frac{n!}{(n-4)!}.
\]
Multiplying both sides by $(n-4)!5!/n!$ yields
\[
n-4 \leq 5!,
\]
or $n \leq 5! + 4 = 124$.  Consequently, any deck that allows the trick to
work contains \emph{at most} $124$ cards.

To show that the trick indeed works with a 124-card deck, we use
part~(\ref{a}).

Construct the bipartite graph $G=(V_1,V_2,E)$, where $V_1$ is the set of
5-card hands, $V_2$ is the set of sequences of 4 cards, and an edge
in $E$ connects a hand $u\in V_1$ to a sequence $v\in V_2$ if $v$ can be
obtained by removing a card from $u$ and arranging the 4 remaining
cards in sequence.

The degree of every node in $V_1$ is $P(5,4)=120$, since there are
$P(5,4)$ 4-card sequences from a set of 5 cards.

The degree of every node in $V_2$ is also $120$, since there are exactly
$120=124-4$ other cards in the 124-card deck that can be added to the
sequence of 4 cards to make a 5-card hand.

Therefore, by part~(\ref{a}), a perfect matching exists.  Thus, given any
hand, there is a way of removing a card and arranging the remaining 4
cards in a sequence so that the sequence uniquely identifies the hand.
This is precisely what's needed for the trick to work.}

\end{problemparts}
\end{problem}

\iffalse

\begin{problem} 
\begin{problemparts}
\problempart How many different permutations are there of the word
``MISSISSIPPI''?

\solution{
\[
\dbinom{11}{1,4,4,2} =\frac{11!}{1!4!4!2!} = 34650
\]
}

\problempart Suppose we have a generalized $n$-letter ``MISSISSIPPI''
word whose letters break down as follows: $m$ occurrences of ``M'',
$i$ occurrences of ``I'', $s$ of ``S'', and $p$ of ``P''.  For
example, for ``MISSISSIPI'' from the previous part, $(n,m,i,s,p) =
(11,1,4,4,2)$.\footnote{Reminder:
$\binom{r_1 + r_2 + \dots + r_n}{r_1, r_2, \dots, r_n}
= 
\frac{(r_1 + r_2 + \dots + r_n)!}{r_1! \ r_2! \ \dots \ r_n!}$
}


Identify which formulas among the following describe the number of
different permutations of the generalized ``MISSISSIPI'' word:

\begin{enumerate}

\item	$\dbinom{n}{m,i,s,p}$

\solution{True. This is a straightforward application of Theorem~6.2
in Course Notes~8.}

\item	$\dbinom{n}{p,i,m,s}$

\solution{True. The order of the lower arguments of the multinomial
coefficient is not important.}

\item	$\dbinom{n}{m,i,s,n-m-i-s}$

\solution{True. Because $m+i+s+p=n$, so $p=n-m-i-s$.}

\item	$\dbinom{n}{m}\dbinom{n}{i}\dbinom{n}{s}\dbinom{n}{p}$

\solution{False.}

\item	$\dbinom{n}{m}\dbinom{m}{i}\dbinom{i}{s}\dbinom{s}{p}$

\solution{False.}

\item   $\dbinom{n}{m}\dbinom{n-m}{i}\dbinom{n-m-i}{s}\dbinom{n-m-i-s}{p}$

\solution{True. With the same reasoning as the one used in the
alternative proof of Theorem~6.2, in Course Notes~8,~\S6.3.}
\end{enumerate}


\problempart Explain why the formulas you chose are all counting the
same thing. In other words give a {\em combinatorial argument} why the
formulas are equivalent.

\solution{ADD}

\end{problemparts}
\end{problem}


\begin{problem} An adequately-prepared 6.042 student has
the following texts:

\begin{itemize}
\item 5 copies of Velleman
\item 2 copies of Rosen, 3rd edition
\item 6 copies of Rosen, 4th edition
\item 4 copies of the Fall '02 Lecture Notes
\end{itemize}

Copies of the same text are indistinguishable.  The student also has
a bookshelf with four distinguishable shelves.  In how many different
ways can the student arrange his texts on his bookshelf?  Assume that
each shelf has enough space to hold all of the texts and that two
arrangements are different if the texts appear in a different order on
a shelf.

\solution{Each arrangement of the texts on the bookshelf corresponds to
a sequence of the texts together with three ``dividers''.  The texts on
the first shelf appear in the sequence before the first divider, the texts
on the second shelf appear between the first and second dividers, etc.
Thus, the number of different arrangements is $\displaystyle
\binom{20}{5,2,6,4,3}$.
}
\end{problem}


% source: old
% last used: fall 01 pset (similar version, but not same)
% topics: division rule, bijections
\begin{problem}
REMOVE? Suppose that Theory Pig wants to take a walk on his
neighborhood grid to location $(n,n)$. He starts at position $(0, 0)$.
At any time, he can step north (incrementing the first coordinate) or
step east (incrementing the second coordinate).

\begin{problemparts}

\problempart In how many different ways can he reach position $(n,n)$,
where $n$ is a nonnegative integer?

\solution{
Theory Pig must take $2n$ steps in total.  Of these, he must
choose a subset of $n$ to be north steps.  This gives $\binom{2n}{n}$  
different ways to reach $(n, n)$.
}

\problempart 
How many different ways are there to list the numbers $1,2,\ldots,2n$
such that the even numbers appear in increasing order and the odd
numbers appear in decreasing order? 

\solution{ 
There are $(2n)!$ ways to list the numbers $1,2,\ldots,n$.  We can
define a $n!$-to-1 mapping that takes an arbitrary listing to a
listing in which the even numbers are sorted in increasing order 
and the odd numbers remain as before.  Thus, by the Division Rule
there are $(2n)!/n!$ listings in which the even numbers appear in
increasing order.  Similarly, we can define an $n!$-to-1 mapping that
takes a listing in which the even numbers appear in increasing order
and the odd numbers are in an arbitrary order to a listing in which
the even numbers appear in increasing order (as before) and the odd
numbers appear in decreasing order.  Therefore, there are
\begin{eqnarray*}
\frac{(2n)!}{n! \ n!} & = & \binom{2n}{n}
\end{eqnarray*}
listings in which the even numbers are increasing and the odd numbers 
are decreasing.

Yet another argument: Of the total $2n$ positions in the sequence,
there are $\binom{2n}{n}$ ways to choose where the even numbers are
going to be. Once you make this choice, the positions of the odd
numbers are fully specified (just the unoccupied positions) and the
order of both the even and odd numbers is fully specified as
well. So, after this choice, there is exactly one way to determine the 
entire sequence. So there are as many sequences as many choices of
this kind, $\binom{2n}{n}$.
}

\problempart Describe a bijection that maps each one of Theory Pig's
paths to a listing of the numbers $1, 2, \ldots 2n$ with even numbers
increasing and odd numbers decreasing.

\solution{Each time Theory Pig take a step north, write down an even
number, starting with 2 and working up.  Each time Theory Pig takes a
step east, write an odd number, starting with $2n-1$ and working down.}
\end{problemparts}
\end{problem}



% Topics: Stars and Bars
% last used Fall 01 tutorial 9
% pset7 problem8 spring98, exercise $4.6-42$ of Rosen.
\begin{problem}
A shelf holds 13 books in a row. How many ways are there to choose
five books so that no two adjacent books are chosen?

\solution{There are 5 bars (chosen books), and therefore there are 6
places where the 8 stars (non-chosen books) can fit (before the first
bar, between the first and second bars,..., after the fifth bar).
Each of the second through fifth of these slots must have at least one
star in it, so that adjacent books are not chosen. Once we have placed
these 4 stars, there are 4 stars left to be placed in 6 slots. The
number of ways to do this is therefore ${{6+4-1}\choose{4}}={9\choose
4}=126$.}
\end{problem}
\fi

\end{document}
