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

%\hidesolutions         
%\showsolutions
\renewcommand{\coursecopyrightnames}{Dr.~Radhika~Nagpal}

\begin{document}
\inclassproblems{8W}

% Follow up to INCLASS MAGIC TRICK DEMO
% source: from F99 tut16 & S99 tut9
\begin{problem} We just demonstrated how to ``guess'' the fifth
card in a poker hand when a collaborator reveals the other four cards.
Describe a method for guessing two hidden cards in a hand of nine
cards, when your collaborator reveals the other seven cards.

\solution{
There must be $\ceil{9/4} = 3$ cards with the same suit, so 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}
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}

% source: old
% last used: fall 01 pset (similar version, but not same)
% topics: division rule, bijections
\begin{problem}
{\em Repeated from Monday if you did not get a chance to do
it.} 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 non-negative 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}


\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)$.

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 straight forward 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}
\end{problemparts}

{\em 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!}$

\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}

\end{document}



