\documentclass[twoside,12pt]{article}
\usepackage{light}

%\hidesolutions
\showsolutions

\begin{document}

\problemset{8}{April 5, 2005}{Monday, April 11 at 9 PM in Room 32-044}

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

\begin{problem}
An electronic toy displays a $4 \times 4$ grid of colored squares.  At
all times, four are red, four are green, four are blue, and four are
yellow.  For example, here is one possible configuration:
%
\begin{center}
\begin{picture}(140,130)(-30,-40)
% \put(-30,-40){\dashbox(140,130){}} % bounding box
\put(40,25){\oval(140,130)}
\multiput(0,0)(20,0){5}{\line(0,1){80}}
\multiput(0,0)(0,20){5}{\line(1,0){80}}
\multiput(0,-20)(20,0){5}{\circle{16}}
\put(0,-20){\makebox(0,0){1}}
\put(20,-20){\makebox(0,0){2}}
\put(40,-20){\makebox(0,0){3}}
\put(60,-20){\makebox(0,0){4}}
\put(80,-20){\makebox(0,0){5}}
{\Large
\put(10,10){\makebox(0,0){B}}
\put(10,30){\makebox(0,0){B}}
\put(10,50){\makebox(0,0){Y}}
\put(10,70){\makebox(0,0){R}}
\put(30,10){\makebox(0,0){G}}
\put(30,30){\makebox(0,0){R}}
\put(30,50){\makebox(0,0){B}}
\put(30,70){\makebox(0,0){B}}
\put(50,10){\makebox(0,0){Y}}
\put(50,30){\makebox(0,0){R}}
\put(50,50){\makebox(0,0){G}}
\put(50,70){\makebox(0,0){Y}}
\put(70,10){\makebox(0,0){Y}}
\put(70,30){\makebox(0,0){G}}
\put(70,50){\makebox(0,0){G}}
\put(70,70){\makebox(0,0){R}}
}
\end{picture}
\end{center}
%

\bparts

\ppart How many such configurations are possible?

\solution{This is equal to the number of sequences containing 4 R's, 4
G's, 4 B's, and 4 Y's, which is:
%
\[
\frac{16!}{(4!)^4}
\]
}

\ppart Below the display, there are five buttons numbered 1, 2, 3, 4,
and 5.  The player may press a sequence of buttons; however, the same
button can not be pressed twice in a row.  How many different
sequences of $n$ button-presses are possible?

\solution{There are 5 choices for the first button press and 4 for
each subsequence press.  Therefore, the number of different sequences
of $n$ button presses is $5 \cdot 4^{n-1}$.}

\ppart Each button press scrambles the colored squares in a
complicated, but nonrandom way.  Prove that there exist two
\textit{different} sequences of 32 button presses that both produce
the \textit{same} configuration, if the puzzle is initially in the
state shown above.

\solution{We use the Pigeonhole Principle.  Let $A$ be the set of all
sequences of 32 button presses, let $B$ be the set of all
configurations, and let $f : A \to B$ map each sequence of button
presses to the configuration that results.  Now:
%
\[
\size{A} > 4^{32} > 16! > \size{B}
\]
%
Thus, by the Pigeonhole Principle, $f$ is not injective; that is,
there exist distinct elements $a_1, a_2 \in A$ such taht $f(a_1) =
f(a_2)$.  In other words, there are two different sequences of button
presses that produce the same configuration}.

\eparts

\end{problem}

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

\begin{problem}
Suppose you have five 6-sided dice, which are colored red, blue,
green, white, and black.  A \textit{roll} is a sequence specifying a
value for each die.  For example, one roll is:
%
\[
(\underbrace{3}_{\text{red}},
\underbrace{1}_{\text{green}},
\underbrace{4}_{\text{blue}},
\underbrace{1}_{\text{white}},
\underbrace{5}_{\text{black}})
\]
%
For the problems below, you do not need to simpify your answers, but
briefly explain your reasoning.

\bparts

\ppart For how many rolls is the value on every die different?

Example: $(1, 2, 3, 4, 5)$ is a roll of this type, but $(1, 1, 2, 3,
4)$ is not.

\solution{The number of such rolls is $6 \cdot 5 \cdot 4 \cdot 3 \cdot 2$}

\ppart For how many rolls do two dice have the same value and the
remaining three dice all have different values?

Example: $(6, 1, 6, 2, 3)$ is a roll of this type, but $(1, 1, 2, 2,
3)$ and $(4, 4, 4, 5, 6)$ are not.

\solution{There are $\binom{5}{2}$ possible pairs of rolls that might
have the same value and 6 possibilities for what this value is.  There
$5 \cdot 4 \cdot 3$ possible distinct values for the remaining three
rolls.  So the number of rolls of this type is
\[
\binom{5}{2} \cdot 6 \cdot 5 \cdot 4 \cdot 3
\]
}

\ppart For how many rolls do two dice have one value, two different
dice have a second value, and the remaining die a third value?

Example: $(6, 1, 2, 1, 2)$ is a roll of this type, but $(4, 4, 4, 4,
5)$ and $(5, 5, 5, 6, 6)$ are not.

\solution{There are $\binom{6}{2}$ sets of two values that might be
duplicated.  There are $\binom{5}{2}$ rolls where larger duplicated value
may come up and $\binom{3}{2}$ remaining rolls where the smaller
duplicated value may come up.  There is only 1 remaining roll where the
nonduplicated value may then come up, and 4 remaining values it could
take.  So, the number of rolls of this type is:
%
\[
\binom{6}{2} \cdot \binom{5}{2} \cdot \binom{3}{2} \cdot 4
\]}

\iffalse
\ppart How many rolls contain five consecutive values in some order?

Example $(4, 2, 5, 6, 3)$ is of this type, but $(1, 4, 2, 6, 5)$ is
not.

\solution{The five consecutive values could be either 1 to 5 or 2 to
  6.  There are $5!$ rolls of each type, so the total number is $2
  \cdot 5!$.}
\fi

\eparts

\end{problem}

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

\begin{problem}
This problem concerns \textit{seven card} hands dealt from a regular
52-card deck.

\bparts

\ppart How many different hands are possible?

\solution{There is one hand for each way of choosing 7 cards from a
52-card deck.  Therefore, the number of possible hands is:
%
\[
\binom{52}{7}
\]
%
by the Subset Rule.
}

\ppart How many hands contain three pairs and no three-of-a-kind or
four-of-a-kind?

\solution{There is a bijection with sequences specifying:
%
\begin{itemize}
\item The values of the pairs, which can be chosen in $\binom{13}{3}$
ways.
\item The suits of the lowest-value pair, which can be chosen in
$\binom{4}{2}$ ways.
\item The suits of the middle-value pair, which can be chosen in
$\binom{4}{2}$ ways.
\item The suits of the highest-value pair, which can be chosen in
$\binom{4}{2}$ ways.
\item The value of the remaining card, which can be chosen in 10 ways.
\item The suit of the remaining card, which can be chosen in 4 ways.
\end{itemize}
%
Thus, the number of seven-card poker hands containing three pairs and
no three or four-of-a-kind is:
%
\[
\binom{13}{3} \cdot \binom{4}{2}^3 \cdot 10 \cdot 4
\]
%
By the Generalized Product Rule.}

\ppart How many hands have all cards of the same suit?

\solution{There is a bijection with sequences specifying:
%
\begin{itemize}
\item The suit of all the cards, which can be chosen in $4$ ways.
\item The values of the cards, which can be chosen in $\binom{13}{7}$
ways.
\end{itemize}
%
So the seven cards can be chosen in $4 \cdot \binom{13}{7}$
ways.}

\ppart How many hands have 5 or more face cards?  (The jacks, queens,
and kings are the face cards.)

\solution{There is a bijection between hands with exactly $k$ face
cards and pairs consisting of:
%
\begin{itemize}
\item A set of $k$ face cards, which can be chosen in $\binom{12}{k}$
ways.
\item A set of $7-k$ numbered cards, which can be chosen in
$\binom{40}{7-k}$ ways.
\end{itemize}
%
Thus, there are $\binom{12}{k} \binom{40}{7-k}$ hands with exactly $k$
face cards.  By the Sum Rule, there are
%
\[
\binom{12}{5} \binom{40}{2} +
\binom{12}{6} \binom{40}{1} +
\binom{12}{7} \binom{40}{0}
\]
%
hands with 5, 6, or 7 face cards.
}

\eparts

\end{problem}

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

\begin{problem}
The lecture notes describe a magic trick in which the audience selects
5 cards from a deck, the Assistant reveals 4 of these cards in some
order, and the Magician determines the last card.

Now suppose there are \textit{two} decks of cards, one with blue backs
and one with green backs.  As before, the audience selects 5 cards.
The Assistant reveals 4 of these cards in some order.  (The Magician
is allowed to look at both sides of these cards.)  The Magician must
determine the suit, value, and back-color of the remaining card.

\bparts

\ppart Prove that this is possible.

\solution{Construct a bipartite graph with a vertex on the left for
every possible \textit{set} of 5 cards and a vertex on the right for
every possible \textit{sequence} of 4 cards.  Put an edge between a
set of 5 cards and a sequence of 4 if every card in the sequence is
also in the set.  In other words, there is an edge between a set of 5
cards and a sequence of 4 if the Assistant can reveal that sequence of
4 provided the audience selects that set of 5.

Now the magic trick is possible if there is a matching for the
vertices on the left.  Specifically, the the audience picks a set of 5
cards.  Then the Assistant reveals the matching sequence of 4 cards.
Finally, the Magician names the remaining card in the matched set.

We can prove the existence of the required matching using Hall's
Theorem directly (as in the notes) or with a corollary (as in
lecture):

\begin{corollary*}
If every vertex on the left side of a bipartite graph has degree $c$
and every vertex on the right has degree $d$, then there is a matching
for the left vertices if $c \geq d > 0$.
\end{corollary*}

Here we'll use the corollary.  In this case, each vertex on the left
has degree $ c= 5 \cdot 4 \cdot 3 \cdot 2 = 120$, since the Assistant
can reveal any one of 5 cards first, 4 cards second, 3 cards third,
and 2 cards last.  Each vertex on the right has degree $d = 104 - 4 =
100$, since the fifth card can be any card in the two decks other than
the four in the sequence.  So a matching for the vertices on the left
exists by the corollary, and the trick can be done.}

\ppart \textbf{Extra credit:} Describe a practical way to perform this
trick.  (We have no solution to this problem!)

\eparts
\end{problem}

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

\begin{problem}
Miss McGillicuddy never goes outside without a collection of pets.  In
particular:
%
\begin{itemize}
\item She brings 3, 4, or 5 dogs.
\item She brings a positive number of songbirds, which always come in
pairs.
\item She may or may not bring her alligator, Freddy.
\end{itemize}
%
Let $T_n$ denote the number of different collections of $n$ pets that
can accompany her.  For example, $T_6 = 2$ since there are 2 possible
collections of 6 pets:
%
\begin{itemize}
\item 3 dogs, 2 songbirds, 1 alligator
\item 4 dogs, 2 songbirds, 0 alligators
\end{itemize}

\bparts

\ppart Give a closed-form generating function for the sequence
$(T_0,\ T_1,\ T_2,\ T_3,\ \ldots)$.

\solution{
\begin{align*}
T(x) & = \underbrace{(x^3 + x^4 + x^5)}_{\text{collections of dogs}} \cdot
         \underbrace{(x^2 + x^4 + x^6 + x^8 + \ldots)}_{\text{collections of songbirds}} \cdot
         \underbrace{(1 + x)}_{\text{collections of gators}} \\
     & = (x^3 + x^4 + x^5) \cdot \frac{x^2}{1 - x^2} \cdot (1 + x) \\
     & = \frac{x^5 + x^6 + x^7}{1 - x}
\end{align*}
%
The second equation follows from the formula for the sum of a
geometric series.  The last step is a simplification.}

\ppart From this generating function, find a closed-form expression
for $T_n$.  (Your answer may involve several cases.)

\solution{
\begin{align*}
\frac{x^5 + x^6 + x^7}{1 - x}
    & = (x^5 + x^6 + x^7) (1 + x + x^3 + x^3 + \ldots) \\
    & = x^5 + 2 x^6 + 3 x^7 + 3x^8 + 3x^9 + \ldots
\end{align*}
%
Therefore, we have:
%
\[
T_n = 
\begin{cases}
0 & 0 \leq n \leq 4 \\
1 & n = 5 \\
2 & n = 6 \\
3 & n \geq 7
\end{cases}
\]
}

\eparts

\end{problem}

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

\begin{problem}
In this problem, we'll use generating functions to solve the recurrence:
%
\begin{align*}
t_0 & = 0 \\
t_1 & = 1 \\
t_n & = 5 t_{n-1} - 6 t_{n-2} && (\text{for } n \geq 2)
\end{align*}

\bparts

\ppart Find a closed-form generating function $F(x)$ for the sequence
%
\[
(t_0, t_1, t_2, \ldots)
\]

\solution{From the recurrence equation, this is precisely the sequence:
%
\[
(0, 1, 5 t_1 - 6 t_0, 5 t_2 - 6 t_1,  5 t_3 - 6 t_2, \ldots)
\]
%
We can express this sequence in terms of the generating function $F(x)$:
%
\[
\begin{array}{ccccccccccl}
 &(& 0, & 5 t_0, & 5 t_1, & 5 t_2, & 5 t_3, & \ldots & )
        & \longleftrightarrow & 5 x F(x) \\
 &(& 0, & 0, & -6 t_0, & -6 t_1, & -6 t_2, & \ldots & )
        & \longleftrightarrow & -6 x^2 F(x) \\
+&(& 0, & 1, & 0, & 0, & 0, & \ldots & )
        & \longleftrightarrow & x \\ \hline
=&(& 0, & 5 t_0 + 1, & 5 t_1 - 6 t_0, & 5 t_2 - 6 t_1, & 5 t_3 - 6 t_2, & \ldots) & \longleftrightarrow & F(x)
\end{array}
\]
%
The second term is correct; $5 t_0 + 1 = 1$, since $t_0 = 0$.  So we
have the equation:
%
\[
F(x) = 5xF(x) - 6x^2F(x) + x
\]
%
Solving this equation for $F(x)$ gives:
%
\[
F(x) = \frac{x}{1 - 5x + 6x^2}
\]
}

\ppart Rewrite this generating function as a sum of fractions of the
form:
%
\[
\frac{c}{1 - r x}
\]
%
where $c$ and $r$ are constants.

\solution{Factoring the denominator gives $1 - 5x + 6x^2 =
(1-2x)(1-3x)$.  So we can rewrite the fraction in the form:
%
\[
\frac{x}{1 - 5x + 6x^2} = \frac{c}{1-2x} + \frac{d}{1-3x}
\]
%
Substituting $x = 0$ gives the equation $c + d = 0$.  Substituting $x
= 1$ gives $1/2 = - c - d/2$ or, equivalently, $2c + d = -1$.  Solving
this system of linear equations gives $c = -1$ and $d = 1$.
Therefore, we have:
%
\[
F(x) = \frac{-1}{1-2x} + \frac{1}{1-3x}
\]
}

\ppart Expand each fraction using the fact:
%
\[
\frac{1}{1 - rx} = 1 + rx + r^2x^2 + r^3x^3 + \ldots
\]
%
Combine these expansions to obtain a closed-form expression for $t_n$.

\solution{
\begin{align*}
F(x) & = -2^0 - 2^1x - 2^2 x^2 - 2^3 x^3 - \ldots \\
     & + \mbox{} 3^0 + 3^1 x + 3^2 x^2 + 3^3 x^3 + \ldots \\
     & = (3^0-2^0) + (3^1-2^1) x + (3^2 - 2^2) x^2 - (3^3 - 2^3) x^3 - \ldots
\end{align*}
%
Thus, $t_n = 3^n - 2^n$.
}

\eparts

\end{problem}

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

\begin{problem}
Below is a combinatorial proof of an equation.  What is the equation?

\begin{proof}
Stinky Peterson owns $n$ newts, $t$ toads, and $s$ slugs.
Conveniently, he lives in a dorm with $n + t + s$ other students.
(The students are distinguishable, but creatures of the same variety
are not distinguishable.)  Stinky wants to put one creature in each
neighbor's bed.  Let $W$ be the set of all ways in which this can be
done.

On one hand, he could first determine who gets the slugs.  Then, he
could decide who among his remaining neighbors has earned a toad.
Therefore, $|W|$ is equal to the expression on the left.

On the other hand, Stinky could first decide which people deserve
newts and slugs and then, from among those, determine who truly merits
a newt.  This shows that $|W|$ is equal to the expression on the
right.

Since both expressions are equal to $|W|$, they must be equal to each
other.
\end{proof}

(Combinatorial proofs are real proofs.  They are not only rigorous,
but also convey an intuitive understanding that a purely algebraic
argument might not reveal.  However, combinatorial proofs are usually
less colorful than this one.)

\solution{
\[
\binom{n + t + s}{s} \cdot \binom{n + t}{t}
    = \binom{n + t + s}{n + s} \cdot \binom{n + s}{n}
\]}

\end{problem}

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

\begin{problem}
Consider the following equation:
%
\begin{equation*}
\label{eq:star}
\binom{2n}{n+1} = \sum_{k=0}^{n-1} \binom{n}{k} \binom{n}{k+1} \tag{*}
\end{equation*}

\bparts

\ppart Describe a set $S$ of binary sequences whose size is given by
the expression on the left.

\solution{Let $S$ be all $2n$-bit sequences with exactly $n + 1$ ones.}

\ppart Describe a way of partitioning $S$ into disjoint subsets $T_0,
\ldots, T_{n-1}$ such that:
%
\[
\size{T_k} = \binom{n}{k} \binom{n}{k+1}
\]
%
In particular, state clearly which elements of $S$ are in set $T_k$
and explain why $\size{T_k}$ satisfies this equation.

\solution{Let $T_k$ consist of $2n$-bit sequences with exactly $k$
zeros in the first $n$ positions.  Each such sequence has $n - k$ ones
in the first $n$ positions, and thus $k + 1$ ones in the last $n$
positions.  There are $\binom{n}{k}$ ways to select the first $n$ bits
and $\binom{n}{k+1}$ ways to select the last $n$ bits, and so there
are $\binom{n}{k} \binom{n}{k+1}$ elements of $T_k$ in all.}

\ppart Explain why equation~\eqref{eq:star} logically follows.

\solution{Since $S$ is equal to the disjoint union $T_0 \cup \ldots
\cup T_{n-1}$, the sum rule implies:
%
\[
\size{S} = \size{T_0} \cup \ldots \cup \size{T_{n-1}}
\]
%
Substituting the results from the two preceding parts gives
equation~\eqref{eq:star}.}

\eparts

\end{problem}

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

\end{document}
