\Question
\textbf{Counting, Counting, and More Counting (32 points)}\\
The only way to learn counting is to practice, practice, practice, so
here is your chance to do so.
We encourage you to leave your answer as an expression (rather than
trying to evaluate it to get a specific number).
\begin{enumerate}
\item How many 10-bit strings are there that contain exactly 4 ones?
\item How many different 13-card bridge hands are there?
(A bridge hand is obtained by selecting 13 cards from a standard
52-card deck. The order of the cards in a bridge hand is
irrelevant.)
\item How many different 13-card bridge hands are there that contain
no aces?
\item How many different 13-card bridge hands are there that contain
all four aces?
\item How many different 13-card bridge hands are there that contain
exactly 6 spades?
\item How many 99-bit strings are there that contain more ones than
zeros?
\item How many different anagrams of FLORIDA are there? (An anagram
of FLORIDA is any re-ordering of the letters of FLORIDA, i.e., any
string made up of the letters F, L, O, R, I, D, and A, in any order.
The anagram does not have to be an English word.)
\item How many different anagrams of ALASKA are there?
\item How many different anagrams of ALABAMA are there?
\item How many different anagrams of MONTANA are there?
\item If we have a standard 52-card deck, how many ways are there to
order these 52 cards?
\item Two identical decks of 52 cards are mixed together, yielding a
stack of 104 cards.
How many different ways are there to order this stack of 104 cards?
\item We have 9 balls, numbered 1 through 9, and 27 bins.
How many different ways are there to distribute these 9 balls among
the 27 bins? Assume the bins are distinguishable (e.g., numbered 1
through 27).
\item We throw 9 identical balls into 7 bins.
How many different ways are there to distribute these 9 balls among
the 7 bins such that no bin is empty? Assume the bins are
distinguishable (e.g., numbered 1 through 7).
\item How many different ways are there to throw 9 identical balls
into 27 bins? Assume the bins are distinguishable (e.g., numbered 1
through 27).
\item There are exactly 20 students currently enrolled in a class.
How many different ways are there to pair up the 20 students, so
that each student is paired with one other student?
\end{enumerate}
\Question
\textbf{Counting (2/3/5/5 points)}
\begin{enumerate}
\item How many ways are there to arrange $n$ 1s and $k$ 0s into a sequence?
\item How many solutions does
$ x_0 + x_1 + \ldots + x_k = n $
have, if all $x$s must be non-negative integers?
\item How many solutions does
$ x_0 + x_1 = n $
have, if all $x$s must be \emph{strictly positive} integers?
\item How many solutions does
$ x_0 + x_1 + \ldots + x_k = n $
have, if all $x$s must be \emph{strictly positive} integers?
\end{enumerate}
\Question
\textbf{Fermat's Necklace (2/3/5/5 points)}\\
Let $p$ be a prime number and let $k$ be a positive integer. We have an endless supply of beads. The beads come in
$k$ different colors. All beads of the same color are indistinguishable.
\begin{enumerate}
\item We have a piece of string. As a relaxing study break, we want to make a
pretty garland by threading $p$ beads onto the string.
How many different ways are there construct such a sequence of $p$ beads of $k$ different colors?
\item Now let's add a restriction. We want our garland to be exciting and multicolored. Now
how many different sequences exist?
(Your answer should be a simple function of $k$ and $p$.)
\item Now we tie the two ends of the string together, forming a circular
necklace which lets us freely rotate the beads around the necklace.
We'll consider two necklaces equivalent if the sequence of colors on one
can be obtained by rotating the beads on the other.
(For instance, if we have $k=3$ colors---red (R), green (G), and
blue (B)---then the length $p = 5$ necklaces RGGBG, GGBGR, GBGRG, BGRGG, and GRGGB are all
equivalent, because these are cyclic shifts of each other.)
How many non-equivalent sequences are there now? Again, the $p$
beads must not all have the same color.
(Your answer should be a simple function of $k$ and $p$.)
[Hint: What follows if rotating all the beads on a necklace to another
position produces an identical looking necklace?]
\item Use your answer to part (c) to prove Fermat's little theorem.
(Recall that Fermat's little theorem says that if $p$ is prime and
$a \not\equiv 0 \pmod p$, then $a^{p-1} \equiv 1 \pmod p$.)
\end{enumerate}
\Question
\textbf{Maze (5/5 points)}
Let's assume that Tom is located at the bottom left corner of the maze below,
and Jerry is located at the top right corner. Tom of course wants to get to
Jerry by the shortest path possible.
\begin{figure*}[htbp]
\vspace{-0.5em}
\centering
{
\hspace{0em}\includegraphics[width=0.5\linewidth]{src/problems/counting/resources/figures/maze.png}
}
\vspace{-0.5em}
%\caption{\label{probability-plots}}
\vspace{-0.5em}
\end{figure*}
\begin{enumerate}[a)]
\item How many such shortest paths exist?
\item How many shortest paths pass through the edge labelled $X$?
\item \textbf{(Optional)} The edge labelled $Y$? Both the edges $X$ and $Y$? Neither edge $X$ nor edge $Y$?
\item \textbf{(Optional)} How many shortest paths pass through the vertex labelled $Z$? The vertex labelled $W$? Both the vertices $Z$ and $W$? Neither vertex $Z$ nor vertex $W$?
\end{enumerate}
\Question
\textbf{Story Problems (5/5/5/5 points)}
\newcommand{\sblank}{\vspace{1in}}
Prove the following identities by combinatorial argument:
\begin{enumerate}
\item $$ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} $$
\item $$ \binom{2n}{2} = 2 \binom{n}{2} + n^2. $$
\item (Hint: Consider how many ways there are to pick groups of people ("teams") and then a representative ("team leaders").)
$$\sum_{k=0}^n k {n \choose k} = n2^{n-1}$$
\item (Hint: consider a generalization of the previous part.)
$$\sum_{k=j}^n {n \choose k} {k \choose j} = 2^{n-j} {n \choose j}$$
\end{enumerate}
\Question \textbf{Sample Space and Events (1/1/1/1/1/1/2/2 points)} \\
Consider the sample space $\Omega$ of all outcomes from flipping a coin $3$ times.
\begin{Parts}
\Part List all the outcomes in $\Omega$. How many are there?
\Part Let $A$ be the event that the first flip is a heads. List all the outcomes
in $A$. How many are there?
\Part Let $B$ be the event that the third flip is a heads. List all the outcomes
in $B$. How many are there?
\Part Let $C$ be the event that the first and third flip are heads. List all
outcomes in $C$. How many are there?
\Part Let $D$ be the event that the first or the third flip is heads. List all
outcomes in $D$. How many are there?
\Part Are the events $A$ and $B$ disjoint? Express $C$ in terms of $A$ and
$B$. Express $D$ in terms of $A$ and $B$.
\Part Suppose now the coin is flipped $n \ge 3$ times instead of $3$
flips. Compute $|\Omega|, |A|,|B|,|C|,|D|$.
\Part
Your gambling buddy found a website online where he could buy trick coins that
are heads or tails on both sides. He puts three coins into a bag: one coin that
is heads on both sides, one coin that is tails on both sides, and one that is
heads on one side and tails on the other side. You shake the bag, draw out a
coin at random, put it on the table without looking at it, then look at the side
that is showing. Suppose you notice that the side that is showing is heads.
What is the probability that the other side is heads? Show your work. (Hint:
the answer is NOT 1/2).
\end{Parts}
\Question \textbf{To Be Fair (10 points)}
Suppose you have a biased coin with $P(heads) \neq 0.5$. How could
you use this coin to simulate a fair coin? (Hint: Think about pairs
of tosses.)