\Question{More Countability}
Given:
\begin{itemize}
\item $A$ is a countable, 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 $A \cap B$
\Part $A \cup B$
\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$
\end{Parts}
\Question{Interval Bijection Construction}
\begin{Parts}
\Part Construct a bijective function $f: [0,1] \rightarrow (0,1]$.
\Part Construct a bijective function $g: [0,1] \rightarrow (0,1)$.
\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{Printing All $x$ where $M(x)$ Halts}
\begin{Parts}
\Part 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}
\Part
Lexicographical ordering of strings means
(1) shorter strings are in front of longer strings and
(2) for two strings of the same length, they are sorted in alphabetical order.
Prove that it's impossible to solve the above problem if we require
the output be in lexicographical order.
\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.
\nosolspace{0.5in}
\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.
\nosolspace{0.5in}
\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.
\nosolspace{0.5in}
\end{Parts}
\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 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 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 How many different anagrams of ABCDEF are there if: (1) C is the left neighbor of E; (2) C is on the left of E.
\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? (Again, you are only allowed to move up or right.)
\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}