\documentclass[12pt,oneside]{article}

\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{graphics}
\input{macros-course}

\begin{document}

%\exam{\ Midterm Exam}{November 4, 1998}
%\newcommand{\solution}[1]{}
%\newcommand{\sol}[1]{}
%\newcommand{\examonly}[1]{#1}
%\newcommand{\us}[1]{#1}

\exam{Midterm Solutions}{November 4, 1998}
\newcommand{\solution}[1]{\bigskip #1}
\newcommand{\sol}[1]{#1}
\newcommand{\examonly}[1]{}
\newcommand{\us}[1]{\underline{#1}}

\newcommand{\unspace}{\vspace{-0.75ex}}

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

\examonly{
\setcounter{page}{0}

\vspace{0.5in}

{\bf WRITE YOUR NAME HERE:}  \underline{\hspace{3in}}

\vspace{0.5in}

\begin{itemize}
\item This exam is open book, open notes.

\item {\bf Show your work as fully and as clearly as possible};
partial credit will be given.

\item Write you solutions in the spaces provided.  If you run out of
space, use the back of the page.

\item Do not discuss this exam with students who have not yet taken
it.
\end{itemize}

\[
\begin{array}{|c|c|c|} \hline
\text{Problem} & \text{Points} & \text{Score} \\
 \hline 1 & 6 & \\
 \hline 2 & 12 & \\
 \hline 3 & 12 & \\
 \hline 4 & 12 & \\
 \hline 5 & 5 & \\
 \hline 6 & 8 & \\
 \hline 7 & 8 & \\
 \hline 8 & 8 & \\
 \hline 9 & 5 & \\
 \hline 10 & 10 & \\
 \hline 11 & 6 & \\
 \hline 12 & 8 & \\ \hline
\text{TOTAL}	& 100	& \\ \hline
\end{array}
\]

\newpage
}

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

\begin{problems}

\problem  {\bf (6 points)} Consider the following proposition.

\[
\forall x \forall y \ (x < y \rightarrow \exists z \ (x < z \wedge z < y))
\]

\begin{problemparts}

\problempart {\bf (2 points)}  Prove or disprove this proposition,
assuming that the universe is the set of integers.

\examonly{\vspace{2 in}}

\solution{ The proposition is false.  In the case where $x = 0$ and $y
= 1$, there does not exist an integer $z$ such that $x < z$ and $z <
y$.  }

\problempart {\bf (4 points)}  Write the negation of this proposition.
Your solution may {\em not} use the $\neg$ symbol, but may use any of
the relations $=$, $<$, $>$, $\leq$, or $\geq$.

\examonly{\vspace{1.0 in}}

\solution{
\[
\exists x \exists y \ (x < y \wedge \forall z \ (x \geq z \vee z \geq y))
\]
}

\end{problemparts}

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

\examonly{\newpage}

\problem {\bf (10 points)} Define the matrix

\begin{eqnarray*}
M & = & \left[
\begin{array}{cc}
0 & 1 \\
1 & 1
\end{array}
\right].
\end{eqnarray*}

Let $M^n$ denote the product of $n$ copies of the matrix $M$.  Use
ordinary induction to prove that for all $n \geq 1$, the upper right
entry of $M^n$ is $F_n$, the $n$-th Fibonacci number.  State your
inductive hypothesis clearly.

For reference, the standard formula for the product of $2 \times 2$
matrices is given below.

\begin{eqnarray*}
\left[
\begin{array}{cc}
a & b \\
c & d
\end{array}
\right]
\cdot
\left[
\begin{array}{cc}
e & f \\
g & h
\end{array}
\right]
& = &
\left[
\begin{array}{cc}
ae + bg & af + bh \\
ce + dg & cf + dh
\end{array}
\right]
\end{eqnarray*}

Recall that $F_0 = 0$, $F_1 = 1$, $F_2 = 1$, $F_3 = 2$, \ldots.

\solution{
\begin{proof}
The proof is by induction.  Let $P(n)$ be the proposition that

\begin{eqnarray*}
M^n & = & \left[
\begin{array}{cc}
F_{n-1} & F_n \\
F_n & F_{n+1}
\end{array}
\right].
\end{eqnarray*}

In the base case, $P(1)$ is true because

\begin{eqnarray*}
M^1 & = & 
\left[
\begin{array}{cc}
0 & 1 \\
1 & 1
\end{array}
\right] \\
& = &
\left[
\begin{array}{cc}
F_0 & F_1 \\
F_1 & F_2
\end{array}
\right].
\end{eqnarray*}
\end{proof}

In the inductive step, for $n \geq 1$ assume $P(n)$ to prove $P(n+1)$.
The following equalities hold.

\begin{eqnarray*}
M^{n+1} & = &	M^n \cdot M \\
	& = &	\left[
		\begin{array}{cc}
		F_{n-1} & F_n \\
		F_n & F_{n+1}
		\end{array}
		\right] \cdot
		\left[
		\begin{array}{cc}
		0 & 1 \\
		1 & 1
		\end{array}
		\right] \\
	& = &	\left[
		\begin{array}{cc}
		F_n & F_{n-1} + F_n \\
		F_{n+1} & F_n + F_{n+1}
		\end{array}
		\right] \\
	& = &	\left[
		\begin{array}{cc}
		F_n & F_{n+1} \\
		F_{n+1} & F_{n+2}
		\end{array}
		\right]
\end{eqnarray*}

The first step uses the definition of $M^n$.  The second step uses the
induction hypothesis and the definition of the matrix $M$.  We carry
out a matrix multiplication in the third step and use the Fibonacci
recurrence in the last step.  This shows that $P(n)$ implies $P(n+1)$,
and the claim is proved by induction.
}

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

\examonly{\newpage}

\problem {\bf (12 points)} The vertices of a directed graph can be
partitioned into {\em strongly-connected components}.  Two vertices
$u$ and $v$ belong to the same strongly connected component if there
is a path from $u$ to $v$ and a path from $v$ to $u$.  A strongly
connected component may consist of a single vertex.

Theory Pig has noticed a strange phenomenon.  He starts with a
directed graph and partitions the vertices into strongly-connected
components.  He then removes all edges that connect two vertices in
the same strongly-connected component.  The resulting graph always
seems to be acyclic.

An example is worked out in the figure below.  The original directed
graph is shown on the left.  The vertices $a$, $b$, and $c$ form one
strongly-connected component.  The single vertex $d$ forms a second
strongly-connected component.  Theory Pig removes the edges $a
\rightarrow b$, $b \rightarrow c$, and $c \rightarrow a$, since these
edges connect vertices in the same strongly-connected component.  The
resulting graph is shown on the right.  Note that this graph is
acyclic.

\bigskip

\centerline{\resizebox{!}{1.5in}{\includegraphics{scc.eps}}}

\bigskip

Use proof by contradiction to show that for every directed graph,
application of Theory Pig's procedure gives a directed acyclic graph.

\solution{
\begin{proof}
Let $G = (V,E)$ be an arbitrary directed graph.  Let $G' = (V,E')$ be
the directed graph that remains after we remove all edges that connect
two vertices in the same strongly-connected component.

The proof is by contradiction.  Suppose that $G'$ is not acyclic.
Then let $u$ and $v$ be consecutive nodes in a directed cycle.  There
is a path from $u$ to $v$ consisting of a single edge.  There also is
a path from $v$ to $u$, because the nodes are in a cycle.  Since every
edge in $G'$ is also in $G$, these same two paths exist in the
original graph $G$.  Therefore, $u$ and $v$ are in the same
strongly-connected component of $G$.  But then the edge from $u$ to
$v$ should have been removed during the construction of $G'$.  Since
the the edge was not removed, we have a contradiction.  Therefore,
$G'$ is acyclic.
\end{proof}
}

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

\examonly{\newpage}

\problem {\bf (12 points)} One of the three monks working on the famed
Towers of Hanoi project recently rubbed his pained back and burst out,
``Yo!  What are we doing?  This is for chumps!  Let's punt!''  But
before wandering off to start up fast food joints, they must evenly
divide the monastery's collection of prayer beads.

Initially, monk $A$ has 5 beads, monk $B$ has 3 beads, and monk $C$
has 4 beads.  The monastic order has strict rules regarding the
exchange of prayer beads.  Only the following transactions are
allowed.

\begin{enumerate}

\item Monk $B$ may give a bead to monk $A$ at any time.

\item If $C$ has an odd number of beads, then monk $A$ may give a bead to
monk $B$.

\item If $C$ has an even number of beads or monk $A$ has at least two more
beads then monk $B$, then monk $C$ may give or take a bead from either
monk $A$ or monk $B$.
\end{enumerate}

\begin{problemparts}
\problempart {\bf (3 points)}  Model the situation with a state machine.
Define the set of states,the set of start states, and the set of
transitions.

\examonly{\vspace{2.5in}}

\solution{ The set of states $Q$ consists of all triples $(a, b, c)$
such that $a, b, c \geq 0$ and $a + b + c = 12$.  The set of starts
states $Q_0$ consists of the single triple $(5, 3, 4)$.  The set
$\delta$ contains six types of transition:

\[
\begin{array}{rcll}
(a, b, c) & \rightarrow & (a+1, b-1, c) &
	\quad \text{($b > 0$)} \\
\\
(a, b, c) & \rightarrow & (a-1, b+1, c) &
	\quad \text{($a > 0$ and $c$ is odd)} \\
\\
(a, b, c) & \rightarrow & (a-1, b, c+1) &
	\quad \text{($a > 0$ and either $c$ is even or $a \geq b + 2$)} \\
(a, b, c) & \rightarrow & (a, b-1, c+1) &
	\quad \text{($b > 0$ and either $c$ is even or $a \geq b + 2$)} \\
(a, b, c) & \rightarrow & (a+1, b, c-1) &
	\quad \text{($c > 0$ and either $c$ is even or $a \geq b + 2$)} \\
(a, b, c) & \rightarrow & (a, b+1, c-1) &
	\quad \text{($c > 0$ and either $c$ is even or $a \geq b + 2$)}
\end{array}
\]
}

\problempart {\bf (3 points)}  Prove that the monks can reach the state
where monk $A$ has 0 beads, monk $B$ has 9 beads, and monk $C$ has 3
beads by describing a sequence of steps leading to this state.

\solution{
Initially, monk $C$ gives a bead to monk $B$ using rule 3.  Then monk
$A$ gives his 5 beads to monk $B$ using rule 2 repeatedly. }

\examonly{\newpage}

\problempart {\bf (6 points)}  Prove that the monks can not reach the state
where every monk has 4 beads by using the Invariant Theorem.

\solution{
\begin{proof}
The proof uses the Invariant Theorem.  We prove that if monk $C$ has
an even number of beads, then monk $A$ has more beads than monk $B$.
This implies that the monks can never evenly divide up the prayer
beads; an even division would require that $C$ have 4 beads, but then
the invariant would imply that $A$ has more beads then $B$.

The invariant holds in the single start state $Q_0$, since in this
case monk $C$ has an even number of beads (4), and monk $A$ has more
beads than monk $B$ (5 vs. 3).  Furthermore, if the invariant holds
before a transition, then it holds after a transition.  There are six
cases to check, corresponding to the six types of transition.

\begin{enumerate}
\item $(a, b, c) \rightarrow (a+1, b-1, c)$ where $b > 0$.  If $c$ is
odd, then the invariant holds after the transition because the
hypothesis of the invariant if false.  If $c$ is even, then the
invariant holds after the transition because $a + 1 > a > b > b - 1$.

\item $(a, b, c) \rightarrow (a-1, b+1, c)$ where $a > 0$ and $c$ is
odd.  The invariant holds after the transition because the hypothesis
of the invariant is false.

\item $(a, b, c) \rightarrow (a-1, b, c+1)$ where $a > 0$ and either
$c$ is even or $a \geq b + 2$.  If $c$ is even, then the invariant
holds after the transition because the hypothesis is false.  If $c$ is
odd, then the invariant holds after the transition because the
conclusion is true; that is, monk A has more beads than monk B.
\end{enumerate}

The argument in the remaining three cases is identical to the argument
for case 3.  Since the invariant hold in all start states and is
maintained under all transitions, the claim is proved by the Invariant
Theorem.
\end{proof}
}

\end{problemparts}

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

\examonly{\newpage}

\problem {\bf (5 points)} Find a closed-form expression equal to the
following summation.

\[
\sum_{j=1}^n \sum_{i=0}^{\infty} \sqrt{j} \cdot
	\left( 1 - \frac{1}{2\sqrt{j}} \right)^i
\]

\solution{
\begin{eqnarray*}
\sum_{j=1}^n
	\sum_{i=0}^{\infty}
		\sqrt{j} \cdot \left( 1 - \frac{1}{2\sqrt{j}} \right)^i
	& = &
\sum_{j=1}^n \frac{\sqrt{j}}{1 - \left( 1 - \frac{1}{2\sqrt{j}} \right)} \\
	& = &	2 \cdot \sum_{j=1}^n j \\
	& = &	2 \cdot \frac{n (n+1)}{2} \\
	& = &	n (n + 1)
\end{eqnarray*}

First, we use the formula for the sum of an infinite geometric series
to eliminate the inner summation.  After simplifying, we apply the
formula for the sum of an arithmetic series.}


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

\newpage

\problem {\bf (8 points)}  Order the functions listed below so that each
function is either $O$ or $\Theta$ of the next function.  Indicate
whether the stronger $\Theta$ relationship holds in each case.  No
proofs are required.

\begin{itemize}
\item $F_n$, the $n$-th Fibonacci number
\item $G(n)$, the number directed graphs with vertices
 $\{ 1, 2, 3, \ldots, n \}$ (self-loops permitted)
\item $P(n)$, the number of permutations of an $n$-element set
\item $M(n)$, the number of $n \times n$ matrices with only 0's and 1's
as elements
\end{itemize}

\solution{We rewrite these quantities in simpler forms to make
comparison possible.  First, $F_n$, the $n$-th Fibonacci number is
equal to:

\begin{eqnarray*}
F_n & = & \frac{1}{\sqrt{5}} \left( \frac{1 + \sqrt{5}}{2} \right)^n
	- \frac{1}{\sqrt{5}} \left( \frac{1 - \sqrt{5}}{2} \right)^n \\
	& = &	\Theta\left(\left(\frac{1 + \sqrt{5}}{2}\right)^n\right)
\end{eqnarray*}

The $\Theta$ relation holds because the second term on the right
approaches zero.  The quantity $(1 + \sqrt{5}) / 2$ is $1.618\ldots$,
but any approximation between 1 and 2 will suffice for this problem.

Next, consider $G(n)$.  The possible edge sets of a directed graph
with vertices $\{1, 2, 3, \ldots, n\}$ are the subsets of $\{ 1, 2, 3,
\ldots, n \} \times \{ 1, 2, 3, \ldots, n \}$.  By the product rule and
the formula for the size of a power set, there are $2^{n^2}$ possible
directed graphs.

The number of permutations of an $n$-element set, $P(n)$, is $n!$,
which is bounded above and below by

\begin{eqnarray*}
\left( \frac{n}{e} \right)^n & \leq n! \leq & \left( \frac{n+1}{e} \right)^{n+1}.
\end{eqnarray*}

The number of entries in an $n \times n$ matrix is $n^2$ by the
product rule.  Therefore, $M(n)$, the number of $n \times n$ matrices
with 0-1 entries, is $2^{n^2}$

Putting all these facts together, we find that:

\begin{eqnarray*}
F_n	& = &	O(P(n)) \\
P(n)	& = &	O(G(n)) \\
G(n)	& = &	\Theta(M(n)) \\
\end{eqnarray*}
}

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

\examonly{\newpage}

\problem {\bf (8 points)}  The inhabitants of Xoros 19 are unsatisfied
with the performance of their Fritolator devices.  They have
constructed a factory to convert Fritolators into new, more deadly
craft.  Each day, the factory performs one of the following
conversions:

\begin{eqnarray*}
\text{1 Fritolator} & \rightarrow & \text{1 Pringlizer} \\
\text{2 Fritolators} & \rightarrow & \text{1 Tostitomatic} \\
\text{2 Fritolators} & \rightarrow & \text{1 Santitotron}
\end{eqnarray*}

Grzzwk, the ruler of Xoros 19, plans to use the factory to convert his
entire fleet of $n$ Fritolators.  However, he must decide the sequence
of ships that the factory will produce.  Such a sequence is called a
{\em conversion schedule}.  For example, there are 5 possible
conversion schedules for a fleet of $n = 3$ Fritolators:

\begin{enumerate}
\item Pringlizer, Pringlizer, Pringlizer
\unspace
\item Pringlizer, Tostitomatic
\unspace
\item Pringlizer, Santitotron
\unspace
\item Tostitomatic, Pringlizer
\unspace
\item Santitotron, Pringlizer
\unspace
\end{enumerate}

\bigskip

\begin{problemparts}

\problempart {\bf (4 points)} Let $x_n$ be the number of possible conversion
schedules for a fleet of $n$ Fritolators.  Express $x_n$ with a
recurrence relation and sufficient base cases.

\examonly{\vspace{1in}}

\solution{
If $n = 0$, then there is a single conversion schedule; namely,
produce nothing.  If $n = 1$, then there is still only one conversion
schedule; the factory must produce a Pringlizer.  If $n \geq 2$, then
every conversion schedule is one of the following:

\begin{enumerate}
\item A Pringlizer followed by a conversion schedule for $n-1$ Fritolators.
\item A Tostitomatic followed by a conversion schedule for $n-2$ Fritolators.
\item A Santitotron followed by a conversion schedule for $n-2$ Fritolators.
\end{enumerate}

Thus, for a fleet of $n \geq 2$ Fritolators, there are $x_{n-1} + 2
x_{n-2}$ conversion schedules.  In summary:

\begin{eqnarray*}
x_0 & = & 1 \\
x_1 & = & 1 \\
x_n & = & x_{n-1} + 2 x_{n-2} \quad \text{(for $n \geq 2$)}
\end{eqnarray*}
}

\problempart {\bf (4 points)} Find a closed-form expression for $x_n$, the
number of conversion schedules for a fleet of $n$ Fritolators.

\solution{ The characteristic equation is $r^2 - r - 2 = 0$.  The
roots of this equation are $r = 2$ and $r = -1$.  The general form of
the solution is therefore

\begin{eqnarray*}
x_n	& = &	A 2^n + B (-1)^n
\end{eqnarray*}

Substituting the base cases into this general form gives two linear
equations:

\begin{eqnarray*}
1	& = &	A + B \\
1	& = &	2A - B
\end{eqnarray*}

The solution to this system of equations is $A = \frac{2}{3}$ and $B =
\frac{1}{3}$.  Plugging these constants back into the general form of
the solution gives the exact solution:

\begin{eqnarray*}
x_n	& = &	\frac{2}{3} \cdot 2^n + \frac{1}{3} \cdot (-1)^n
\end{eqnarray*}
}
\end{problemparts}

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

\examonly{\newpage}

\problem {\bf (10 points)}  Solve the following recurrence problems.

\begin{problemparts}

\problempart {\bf (5 points)} Find a closed-form solution to the
following recurrence equation.

\begin{eqnarray*}
y_0 & = & 0 \\
y_1 & = & 1 \\
y_n & = & 7 y_{n-1} - 12 y_{n-2} + 1 \quad \text{(for $n \geq 2$)}
\end{eqnarray*}

\examonly{\vspace{2.5in}}

\solution{ The characteristic equation is $r^2 - 7 r + 12 = 0$.  The
roots of this equation are $r = 3$ and $r = 4$.  Therefore, the
solution to the homogenous equation has the form:

\begin{eqnarray*}
y_n & = & A 3^n + B 4^n
\end{eqnarray*}

The inhomogenous term is a constant, so we first guess a constant
particular solution.  Setting $y_n = c$ gives:

\begin{eqnarray*}
c	& = &	7 c - 12 c + 1 \\
6 c	& = &	1 \\
c	& = &	\frac{1}{6}
\end{eqnarray*}

The complete solution has the form:

\begin{eqnarray*}
y_n	& = &	A 3^n + B 4^n + \frac{1}{6}
\end{eqnarray*}

Substituting the base cases into this general form gives a system of
linear equations:

\begin{eqnarray*}
0	& = &	A + B + \frac{1}{6} \\
1	& = &	3A + 4B + \frac{1}{6}
\end{eqnarray*}

The solution to this system is $A = - \frac{3}{2}$ and $B =
\frac{4}{3}$.  The complete solution to the inhomogenous recurrence is
therefore:

\begin{eqnarray*}
y_n & = & - \frac{3}{2} \cdot 3^n + \frac{4}{3} \cdot 4^n + \frac{1}{6}
\end{eqnarray*}
}

\problempart {\bf (5 points)} Give a $\Theta$ bound on the solution to the
following recurrence.  For reference, $\ln 7 \approx 1.9$ and $\ln 8
\approx 2.1$.

\begin{eqnarray*}
T(n)	& = &	8 T\left(\frac{7n}{8}\right) + n \sqrt{n}
\end{eqnarray*}

\solution{
We use Akra-Bazzi.  First, we find $p$.

\begin{eqnarray*}
8 \cdot \left(\frac{7}{8}\right)^p & = & 1 \\
8 \cdot 7^p & = & 8^p \\
\ln 8 + p \ln 7 & = & p \ln 8 \\
p & = & \frac{\ln 8}{\ln 8 - \ln 7} \\
  & = & 15.572\ldots
\end{eqnarray*}

An integration gives the $\Theta$ bound:

\begin{eqnarray*}
T(n)	& = &	\Theta\left(x^p \cdot
		\left(1 + \int_1^x \frac{u^{3/2}}{u^{p+1}}\ du\right)\right) \\
	& = &	\Theta\left(x^p \cdot \left(1 + u^{3/2 - p}\right)\right) \\
	& = &	\Theta\left(x^p\right)
\end{eqnarray*}

The final step uses the fact that $p \geq \frac{3}{2}$.
}

\end{problemparts}


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

\examonly{\newpage}

\problem {\bf (5 points)}  Suppose that we have functions
$f : A \mapsto B$, $g : B \mapsto C$, and $h : C \mapsto A$ such that
for all $a \in A$, $h(g(f(a))) = a$, and for all $b \in B$,
$f(h(g(b))) = b$.  Proofs are not required for any part of this
problem.

\begin{problemparts}
\problempart {\bf (1 points)}  Which of the functions $f$, $g$, and $h$ must be injective?

\examonly{\vspace{1in}}

\solution{
The functions $f$ and $g$ must injective.  }

\problempart {\bf (1 points)}  Which of the functions $f$, $g$, and $h$ must be surjective?

\examonly{\vspace{1in}}

\solution{
The functions $f$ and $h$ must be surjective.  }

\problempart {\bf (2 points)}  Circle the relations that must hold.

\[
\begin{array}{ccccc}
|B| > |C| &\quad& \us{|C| \geq |A|} &\quad& \us{|B| \leq |C|} \\
\\
\us{|A| = |B|}	&\quad&	|A| \neq |C|		&\quad& |A| + |B| \geq |C|
\\
\end{array}
\]

\problempart {\bf (1 points)}  If $g$ is surjective, then which of the
functions $f$, $g$, and $h$ must be bijective?

\solution{
If $g$ is surjective, then all of the functions must be bijective.
}

\end{problemparts}

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

\examonly{\newpage}

\problem {\bf (10 points}) Indicate whether each of the following sets
is finite (F), countably infinite (CI), or uncountably infinite (UI)
by circling the right answer.  {\em Note that an even quantity is
necessarily finite.}

\bigskip

\begin{tabular}{lccc}
The set of all binary strings with even length.
	& F & \us{CI} & UI \\ \\
The set of all infinite binary strings with 1's in every even position.
	& F & CI & \us{UI} \\
(Odd positions may contain either a 0 or a 1.) \\ \\
The set of all infinite binary strings with an even number of 1's.
	& F & \us{CI} & UI \\ \\
The set of even primes.
	& \us{F} & CI & UI \\ \\
The set of all even-size sets of even-length binary strings.
	& F & \us{CI} & UI \\ \\
\end{tabular}

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

\examonly{\newpage}

\problem {\bf (6 points)}  The Pigeonhole Principle can be used to prove
each of the following statements.  In each case, say what the pigeons
are, what the holes are, and what the function is that maps pigeons to
holes.

{\bf Example.} If I pick five cards from a deck, then I will have at
least two cards from some suit.

Pigeons: The five cards.

Holes: The four suits.

Function: A card is mapped to its suit.

\bigskip

\begin{problemparts}

\problempart {\bf (2 points)}  If everyone in an $n$-player tournament wins
at least one match, then there must be two players with the same
number of wins.

\bigskip

Pigeons:  \solution{The $n$ players in the tournament.}

Holes: \solution{The numbers $1, 2, \ldots, n-1$}

Function:

\solution{A player is mapped to the number of matches that he or she
won.}

\problempart {\bf (2 points)}  This afternoon, 19 pigeons flew through 32
holes in a fence in such a way that at least one pigeon flew through
each of the holes.  Therefore, some pigeon flew through at least two
holes.

\bigskip

Pigeons:  \solution{32 holes}

Holes:  \solution{19 pigeons}

Function:

\solution{A hole is mapped to the first pigeon that flew through it.}

\problempart {\bf (2 points)}  In any collection of six different, non-empty
subsets of $\{a,b,c,d,e\}$, there exist two sets that intersect.

\bigskip

Pigeons: \solution{The six different, non-empty subsets.}

Holes: \solution{The elements $a$, $b$, $c$, $d$, and $e$.}

Function:

\solution{A subset is mapped to the first element in the
list $a$, $b$, $c$, $d$, $e$ that it contains.}

\end{problemparts}

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

\examonly{\newpage}

\problem {\bf (8 points)}  You might be interested to know that 42
students in the class have formed a new living group--- 042 House---
for students who especially enjoy 6.042 and want to talk about it all
the time, even when they are at home.  For this problem, your
solutions may be expressions.

\begin{problemparts}

\problempart {\bf (4 points)} So far at 042 House there have been three
meetings, which house members refer to as $a$, $b$, and $c$.  (That's
the kind of people they are.)  The secretary recorded the following
attendance information.

\begin{itemize}
\item 34 attended meeting $a$
\unspace
\item 32 attended meeting $b$
\unspace
\item 30 attended meeting $c$
\unspace
\item 28 attended meetings $a$ and $b$
\unspace
\item 27 attended meetings $a$ and $c$
\unspace
\item 26 attended meetings $b$ and $c$
\unspace
\item 25 attended meetings $a$, $b$, and $c$
\end{itemize}

How many house members punted all three meetings?

\examonly{\vspace{1.5in}}

\solution{
Let $A$, $B$, and $C$ denote the sets of people that attended meetings
$a$, $b$, and $c$.  The number of people that attended at least one
meeting is $|A \cup B \cup C|$.  We can compute this quantity with the
Inclusion-Exclusion Principle:

\begin{eqnarray*}
|A \cup B \cup C|
	& = &	|A| + |B| + |C|
		- |A \cap B| - |A \cap C| - |B \cap C|
		+ |A \cap B \cap C| \\
	& = &	34 + 32 + 30 - 28 - 27 - 26 + 25 \\
	& = &	40
\end{eqnarray*}

Since 40 people attended at least one meeting, two people punted all
three meetings.  }

\problempart {\bf (2 points)} The 042 House is about to have its first
wild party.  They have identified 23 distinct preparatory chores, such
as working out a good mix of practice problems to entertain the
guests.  One student must be assigned to each chore, and no student
can be assigned to two or more chores.  In how many ways can students
be assigned to chores?

\examonly{\vspace{0.75in}}

\solution{
This is the number of 23-permutations of a 42-element set, which is
$42!/19!$.  }

\problempart {\bf (2 points)}
Theory Pig has decided to visit the living group for 30 days, provided
that one student attend to his needs each day.  A student may attend
to Theory Pig any number of times.  In how many ways can the sequence
of attendants be chosen?

\solution{
There are 42 possible attendants each day.  By the product rule, there
are $42^{30}$ possible sequences of attendants.
} \end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problems} \end{document}
