\Question{More Countability}
Given:
\begin{itemize}
\item $A$ is a countable set, non-empty set. For all $i \in A$, $S_i$ is an uncountable set.
\item $B$ is an uncountable set. For all $i \in B$, $Q_i$ is a countable set.
\end{itemize}
For each of the following, decide if the expression is
"Always Countable", "Always Uncountable", "Sometimes Countable,
Sometimes Uncountable".
For the "Always" cases, prove your claim. For the "Sometimes" case, provide
two examples -- one where the expression is countable, and one where
the expression is uncountable.
\begin{Parts}
\Part $\bigcup_{i \in A} S_i$
\Part $\bigcap_{i \in A} S_i$
\Part $\bigcup_{i \in B} Q_i$
\Part $\bigcap_{i \in B} Q_i$
\Part $A \cap B$
\end{Parts}
\Question{Counting Cartesian Products}
For two sets $A$ and $B$, define the Cartesian Product as $A \times B = \{(a,b) : a \in A, b \in B \}$.
\begin{Parts}
\Part Given two countable sets $A$ and $B$, prove that $A \times B$ is countable.
\Part Given a finite number of countable sets $A_1, A_2, \dots, A_n$, prove that
$A_1 \times A_2 \times \cdots \times A_n$ \\is countable.
\Part Consider an infinite number of countable sets: $B_1, B_2, \dots$. Under what
condition(s) is \\$B_1 \times B_2 \times \cdots$ countable? Prove that if this
condition is violated, $B_1 \times B_2 \times \cdots$ is uncountable.
\end{Parts}
\Question{Impossible Programs}
Show that none of the following programs can exist.
\begin{Parts}
\Part
Consider a program $P$ that takes in any program $F$, input $x$ and output $y$ and returns true if
$F(x)$ outputs $y$ and returns false otherwise.
\Part
Consider a program $P$ that takes in any program $F$ and returns true if $F(F)$ halts and returns
false if it doesn't halt.
\Part
Consider a program $P$ that takes in any programs $F$ and $G$ and returns true if $F$ and $G$ halt
on all the same inputs and returns false otherwise.
\end{Parts}
\Question{Printing All $x$ Where $M(x)$ Halts}
Prove that it is possible to write a program $P$ which:
\begin{itemize}
\item takes as input $M$, a Java program,
\item runs forever, and prints out strings to the console,
\item for every $x$, if $M(x)$ halts, then $P(M)$ eventually prints out $x$,
\item for every $x$, if $M(x)$ does NOT halt, then $P(M)$ never prints out $x$.
\end{itemize}
\Question{Counting, Counting, and More Counting}
The only way to learn counting is to practice, practice, practice, so
here is your chance to do so.
For this problem, you do not need to show work that justifies your answers.
We encourage you to leave your answer as an expression (rather than
trying to evaluate it to get a specific number).
\begin{Parts}
\Part How many 10-bit strings are there that contain exactly 4 ones?
\Part How many ways are there to arrange $n$ 1s and $k$ 0s into a sequence?
\Part 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. \\
How many different 13-card bridge hands are there?
How many different 13-card bridge hands are there that contain
no aces? How many different 13-card bridge hands are there that contain
all four aces? How many different 13-card bridge hands are there that contain
exactly 6 spades?
\Part How many 99-bit strings are there that contain more ones than
zeros?
\Part 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. \\
How many different anagrams of FLORIDA are there? How many different anagrams
of ALASKA are there? How many different anagrams of ALABAMA are there?
How many different anagrams of MONTANA are there?
\Part If we have a standard 52-card deck, how many ways are there to
order these 52 cards?
\Part 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?
\Part 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).
\Part 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).
\Part 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).
\Part 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?
\Part Let (1, 1) be the bottom-left corner and (8, 8) be the upper-right
corner of a chessboard. If you are allowed to move one square at a time and
can only move up or right, what is the number of ways to go from the bottom-left corner to
the upper-right corner?
\Part What is the number of ways to go from the bottom-left corner to
the upper-right corner of the chesssboard, if you must pass through the square
(6, 2), where $(i, j)$ represents the square in the $i$th row from the
bottom and the $j$th column from the left?
\Part How many solutions does $x_0 + x_1 + \cdots + x_k = n$ have, if each $x$ must be a non-negative integer?
\Part How many solutions does $x_0 + x_1 = n$ have, if each $x$ must be a \emph{strictly positive} integer?
\Part How many solutions does $x_0 + x_1 + \cdots + x_k = n$ have, if each $x$ must be a \emph{strictly positive} integer?
\end{Parts}
\Question{Fermat's Necklace}
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{Parts}
\Part 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?
\Part 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$.)
\Part 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$.)
[\textit{Hint}: What follows if rotating all the beads on a necklace to another
position produces an identical looking necklace?]
\Part 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{Parts}