\documentclass[12pt,oneside]{article}

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

\begin{document}

%\examinitials{Quiz 2}{April 15, 2003}
%\newcommand{\solution}[1]{}
%\newcommand{\examonly}[1]{#1}

\exam{Quiz 2 Solutions}{April 17, 2003}
\newcommand{\solution}[1]{\bigskip \textbf{Solution.} #1}
\newcommand{\examonly}[1]{}

\newcommand{\beqn}{\begin{eqnarray*}}
\newcommand{\eeqn}{\end{eqnarray*}}
\newcommand{\ex}[1]{\text{Ex} \left[ #1 \right] }
\newcommand{\pr}[1]{\text{Pr} \left\{ #1 \right\} }

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

\examonly{

\setcounter{page}{0}

\vspace{0.5in}

{\bf Write your name here and on each page:} \underline{\hspace{2.5in}}

\vspace{0.2in}

Circle the name of your tutor:

\begin{center}
\begin{tabular}{ccccc}
\\
Sam Daitch & \hspace{0.5in} & Pedro Felzenszwalb & \hspace{0.5in}
	& Blaise Gassend \\ \\
Jon Jackson & & Attila Kondacs & & Min Wu
\end{tabular}
\end{center}

\vspace{0.25in}

\begin{itemize}
\item This exam is closed book.  Calculators and computers are not
allowed.

\item You may use one handwritten page of notes.  A photocopy of
handwritten notes is not acceptable.

\item Show your work as fully and as clearly as possible so that
partial credit may be given.

\item Write your solutions in the space 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.  Do not leave with a copy of the exam under any circumstances.
\end{itemize}

\vspace{0.25in}

\centerline{\textbf{Good luck!}}

\vspace{0.5in}

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

\begin{problems}

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

\examonly{\newpage}

\newcommand{\tf}[1]{
    \hspace{0.2in}
    \textbf{true}
    \hspace{0.2in}
    \textbf{false}
    \hspace{0.2in}
    \parbox[t]{4.6in}{#1}}

\problem {\bf [16 pts]\ } Next to each statement, circle either {\bf
true} or {\bf false}.

\begin{enumerate}

\item \tf{$((A \rightarrow B) \wedge (B \rightarrow C) \wedge (C
\rightarrow A)) \rightarrow (A \vee B \vee C)$ is a tautology.}

\item \tf{$(\exists x\ \forall y\ P(x, y)) \rightarrow (\forall y\
\exists x\ P(x, y))$ is true for every domain of discourse and every
predicate $P$.}

\item \tf{The relation $\approx$ on the set $\mathbb{R} \times
\mathbb{R}$ defined by $(x, y) \approx (x', y')$ iff $x = x'$ or $y =
y'$ is an equivalence relation.}

\item \tf{If $f : \mathbb{N} \to \mathbb{N}$ and $g : \mathbb{N} \to
\mathbb{N}$ are both injective functions, then the function $h :
\mathbb{N} \to \mathbb{N}$ defined by $h(n) = f(n) + g(n)$ is also
injective.}

\item \tf{If a finite directed graph contains no cycles, then some
vertex has no outgoing edges.  (A self-loop is considered a cycle.)}

\item \tf{Let $R_1$ and $R_2$ be equivalence relations over a set $S$,
and let $\sim$ be a relation over $S$ such that $x \sim y$ iff $x\,R_1\,y$
and $x\,R_2\,y$.  Then $\sim$ is also an equivalence relation.}

\item \tf{Every acyclic, connected, undirected graph without
self-loops and with exactly 175 vertices has exactly 174 edges.}

\item \tf{Suppose that $q$ and $r$ are states of a state machine and
$q \rightarrow r$ is a valid transition.  If $P(q)$ is false and
$P(r)$ is true, then $P$ cannot be an invariant.}

\end{enumerate}

\solution{
\begin{enumerate}

\item {\bf false.}  If $A$, $B$, and $C$ are all false, then the
expression on the left side of the implication is true, but the
expression on the right side is false.  Therefore, the whole statement
is false.

\item {\bf true.}  Suppose that the left side of the implication is
true.  Then there exists some $x_0$ such that $P(x_0, y)$ is true for
all $y$.  This implies that for all $y$, there exists an $x$ (namely,
$x_0$) such that $P(x, y)$ is true.  Thus, the right side is holds.
Therefore, the implication always holds.

\item {\bf false.}  The relation $\approx$ is not transitive.  In
particular, $(0, 0) \approx (0, 1)$ and $(0, 1) \approx (1, 1)$, but
$(0, 0) \not\approx (1, 1)$.

\item {\bf false.}  Let $f(n) = n$ and define $g$ as follows:

\beqn
g(n) & = & \left\{
\begin{array}{ll}
100 - n & \text{(for $n \leq 100$)} \\
n & \text{(for $n > 100$)}
\end{array}
\right.
\eeqn

Then $h(0) = h(1) = \ldots = h(100) = 100$.  Thus, $f$ and $g$ are
injective, but $h$ is not.

\item {\bf false.}  The empty graph (no nodes or vertices) contains no
cycle, and all of its (zero) nodes have outgoing edges. It turns out that 
this was unintentionally a trick question as the statement is true for any
graph other than the empty graph, so everybody got full credit for this
question. For a nonempty graph, the statement is true: pick 
a starting vertex and start following directed
edges (you can always follow directed edges because each node has an
outgoing edge).  If you ever revisit a node, the graph is cyclic; if you never do,
it is not finite.

\item {\bf true.}  The relation $\sim$ is reflexive, symmetric, and
transitive; one can check that it inherits all these properties from
$R_1$ and $R_2$.  If we take symmetry as an example, $x \sim y$ implies $y \sim x$, since
$x\ R_1\ y$ and $x\ R_2\ y$ imply $y\ R_1\ x$ and $y\ R_1\ x$.

\item {\bf true.}  Every acyclic, connected, undirected graph is a
tree.  And for every tree, the number of vertices exceeds the number
of edges by 1.

\item {\bf false.}  An invariant is something which, if it is true, will
remain true as the state machine follows transitions. By this definition, 
it is perfectly possible for an invariant which is initially false to
become true at a later time (it will then remain true forever).

\end{enumerate}
}

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

\examonly{\newpage}

\problem {\bf [14 pts]\ } Use induction to prove that the following
inequality holds for all integers $n \geq 1$.

\beqn
\frac{1 \cdot 3 \cdot 5 \cdots (2n - 1)}{2 \cdot 4 \cdot 6 \cdots (2n)}
& \geq & \frac{1}{2n}
\eeqn

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

\beqn
\frac{1 \cdot 3 \cdot 5 \cdots (2n - 1)}{2 \cdot 4 \cdot 6 \cdots (2n)}
& \geq & \frac{1}{2n}
\eeqn

First, we prove $P(1)$.  In this case, both side of the inequality are
equal to $1/2$, and the inequality $1/2 \geq 1/2$ holds.  Next, for
each $n \geq 1$, we must show that $P(n)$ implies $P(n+1)$.  Assume
that $P(n)$ is true.  Then we can reason as follows:

\beqn
\frac{1 \cdot 3 \cdot 5 \cdots (2n - 1) (2n + 1)}
{2 \cdot 4 \cdot 6 \cdots (2n) \cdot (2n + 2)}
& \geq & \frac{1}{2n} \cdot \frac{2n+1}{2n+2} \\
& > & \frac{1}{2n+2}
\eeqn

\noindent The first step uses the induction hypothesis, $P(n)$.  The
second step uses the fact that $(2n+1) / (2n) > 1$ for all $n \geq 1$.
Therefore, by induction, the proposition $P(n)$ is true for all $n
\geq 1$, and the claim is proved.
\end{proof}
}

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

\examonly{\newpage} 

\problem {\bf [12 pts]\ } For the following problems, the domain of
discourse is the set of all the people in the world.  The predicate
$L(x, y)$ holds if and only if $x$ {\em truly} loves $y$.

\begin{problemparts} 

\problempart {\bf [6 pts]} Translate the statement below into an
English sentence that is as simple as you can make it.

\[
\neg \exists x\ (\ \neg \exists y\ (L(y, x) \wedge x \neq y)\ )
\]

\examonly{\vspace{2.5in}}

\solution{Everyone is truly loved by someone else.}

\problempart {\bf [6 pts]} Translate the statement below into logic
notation.  

\bigskip
\centerline{\em{There is exactly one person in the world that truly
loves himself/herself.}}
\bigskip

In your translation, use only variables, the predicate $L$, and these
symbols:

\[
\exists \quad \forall \quad \neg \quad \wedge \quad \vee \quad \rightarrow \quad \leftrightarrow \quad ( \quad , \quad ) \quad =
\]

\solution{
Many solutions are possible.  Here is one:

\[
\exists x\ (L(x, x) \wedge \forall y\ (L(y, y) \rightarrow x = y))
\]
}
\end{problemparts}

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


\examonly{\newpage}

\problem {\bf [14 pts]} In this problem, the term {\em graph} refers
to an undirected graph without self-loops.  Let $G = (V, E)$ be a
graph such that every vertex has degree at most $k$.  Suppose that $k
+ 1$ colors are available.  Use induction to prove that there is a way
to assign a color to each vertex of $G$ so that for every edge in $G$,
the two vertices joined by that edge are assigned different colors.

\solution{The proof is by induction on the number of vertices in $G$.
Let $P(n)$ be the proposition that every $n$-vertex graph such that
every vertex has degree at most $k$ can be colored with $k+1$ colors
so that the endpoints of every edge are colored differently.  First,
note that $P(0)$ is true; if the graph contains no vertices, then the
claim holds vacuously.

Next, for all $n \geq 0$, we must prove that $P(n)$ implies $P(n+1)$.
Assume that $P(n)$ is true and consider a graph $G$ with $n+1$
vertices and maximum degree $k$.  Pick one vertex $v \in V$.  Let $G'$
be the graph obtained from $G$ by deleting the vertex $v$ and all
edges that touch $v$.  Now, the degree of each vertex in $G'$ is no
greater than the degree of the corresponding vertex in $G$.
Therefore, the maximum degree in $G'$ is at most $k$.  Therefore,
$P(n)$ implies that $G'$ can be colored with $k+1$ colors.  Color each
vertex in $G$ in the same way as the corresponding vertex in $G'$.
All that remains is to color the vertex $v$.  There are $k+1$ colors
available, and $v$ is joined by edges to at most $k$ other vertices.
Therefore, one can color $v$ differently from all the vertices to
which it is joined by an edge.  Therefore, $P(n+1)$ holds, and the
claim is proved by induction.
}

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

\examonly{\newpage} 

\problem {\bf [12 pts]\ } Solve the following problems using the
Pigeonhole Principle.

\begin{problemparts}

\problempart {\bf [6 pts]} A 100-point exam will be given to a class
with 128 students.  The exam can be designed so that every student
receives a score in the range from $k$ to 100.  How large must $k$ be
to ensure that at least three students receive the same score?
Specify the ``pigeons'' and the ``holes'' used in your argument.

\solution{The pigeons are the 128 exams, and the holes are the
possible scores from $k$ to 100.  Each exam is assigned to the score
it receives.  There are $100 - k + 1$ possible score.  By the
Pigeonhole Principle, three students must receive the same score if:

\beqn
128 & \geq & 2 \cdot (100 - k + 1) + 1 \\
k & \geq & \frac{75}{2}
\eeqn

Since $k$ must be an integer, we must choose $k \geq 38$.
}

\examonly{\vspace{2.75in}} 

\problempart {\bf [6 pts]} A dresser drawer in a dark room contains
socks of $n$ different colors.  In particular, there are $k_i \geq 2$
socks of the $i$-th color for $1 \leq i \leq n$.  What is the minimum
number of socks that must you take from the drawer to be certain that
you get at least one matching pair?  Again, specify the ``pigeons''
and the ``holes''.

\solution{The pigeons are the socks taken from the drawer, and the
holes are the $n$ colors.  Each sock is assigned to its color.  By the
Pigeonhole Principle, if $n+1$ socks are taken, then there must be two
socks of the same color. Taking $n$ socks would not be sufficient as each
sock could then be of a different color. Therefore, $n+1$ is the minimum
number of socks that must be taken from the drawer.
}

\end{problemparts}

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

\examonly{\newpage}

\problem {\bf [16 pts]} Each monk entering the Temple of Forever is
given a bowl with 15 red beads and 12 green beads.  Each time the Gong
of Time rings, a monk must do one of two things:

\begin{enumerate}

\item If he has at least 3 red beads in his bowl, then he may remove 3
red beads and add 2 green beads.

\item He may replace each green bead in his bowl with a red bead and
replace each red bead in his bowl with a green bead.

\end{enumerate}

\noindent A monk may leave the Temple of Forever only when he has
exactly 5 red beads and 5 green beads in his bowl.

\begin{problemparts}

\problempart {\bf [4 pts]} Model the life of a monk in the Temple of
Forever as a state machine.  Specify a set of states $Q$, a set of
start states $Q_0$, and a transition relation $\delta$.

\examonly{\vspace{2.75in}}

\solution{The set $Q$ of states is $\mathbb{N} \times \mathbb{N}$.
The set of start states is $Q_0 = \{ (15, 12) \}$.  The transition
relation $\delta$ contains the following transitions for every state
$(r, g) \in Q$.

\beqn
(r, g) & \to & (r - 3, g + 2) \hspace{0.75in} \text{(if $r \geq 3$)} \\
(r, g) & \to & (g, r)
\eeqn
}

\problempart {\bf [4 pts]} Let $r$ be the number of red beads in a
monk's bowl, and let $g$ be the number of green beads.  Is the
property ``$r \neq g$'' an invariant?  Justify your answer.

\solution{No.  The property holds when the monk has 8 red beads and 3
green beads in his bowl.  After a transition of the first type, he has
5 red beads and 5 green beads so the property no longer holds.  Therefore, 
the this property is not an invariant.}

\examonly{\newpage}

\problempart {\bf [4 pts]} Is the property ``$r - g$ is equal to
$5k-3$ or $5k+3$ for some $k \in \mathbb{Z}$'' an invariant?  Justify
your answer.

\examonly{\vspace{3.75in}}

\solution{Yes.  Suppose that the property holds for state $(r, g)$.
Then there exists a $k$ such that $r - g$ is equal to $5k + 3$ or $5k
- 3$.  Now we must check that the property is maintained under the two
types of transition.

\begin{enumerate}

\item After a transition of the first type, the property still holds.
If $r - g = 5k+3$, then $g - r = 5(-k) - 3$; if $r - g = 5k - 3$, then
$g - r = 5(-k) + 3$.

\item After a transition of the second type, the property still holds.
If $r - g = 5k+3$, then $(r - 3) - (g + 2) = 5(k-1)+3$; if $r - g = 5k
- 3$, then $(r - 3) - (g + 2) = 5(k-1) - 3$.

\end{enumerate}

Therefore, the property is an invariant.
}

\problempart {\bf [4 pts]} Use the Invariant Theorem to prove no one
ever leaves the Temple of Forever.

\solution{The invariant above holds for the start state, since $15 -
12 = 5 \cdot 0 + 3$.  However, it does not hold for a bowl with 5 red
beads and 5 green beads, because $5 - 5 = 0$ is not of the form $5k
\pm 3$.  Therefore, this state is not reachable by the Invariant
Theorem.}

\end{problemparts}

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

\examonly{\newpage}

\problem {\bf [16 pts]\ } This problem concerns solutions to the
following equation:

\beqn
4x^3 + 2y^3 & = & z^3
\eeqn

\begin{problemparts}

\problempart {\bf [3 pts]\ } Suppose that $x$, $y$, and $z$ are
positive integers that satisfy the equation.  Show that $z$ must be
even.

\solution{If $x$ and $y$ are integers, then $4x^3 + 2y^3$ is even.
Therefore, $z^3$ is even.  If $z$ was odd, then $z^3$ would be odd, thus
we must conclude that $z$ is even.}

\examonly{\vspace{2.25in}}

\problempart {\bf [3 pts]\ } Show that $y$ must be even.

\solution{Since $z$ is even, $z^3$ is a multiple of 4.  This means
that $z^3 - 4x^3$ is a multiple of 4.  Therefore, $2 y^3$ is a
multiple of 4.  This means that $y^3$ is even, and so $y$ is even ($y$
can't be odd or $y^3$ would be odd as well.}

\examonly{\vspace{2.25in}}

\problempart {\bf [3 pts]\ } Show that $x$ must be even.

\solution{Since $z$ and $y$ are even, $z^3 - 2y^3$ is a multiple of 8.
Therefore, $4x^3$ is a multiple of 8.  This means that $x^3$ is even.
Therefore, $x$ is even ($x$ can't be odd or $x^3$ would be odd as well).}

\examonly{\newpage}

\problempart {\bf [7 pts]\ } Use the well-ordering principle to prove
that there are no positive integer solutions to the equation:

\beqn
4x^3 + 2y^3 & = & z^3
\eeqn

\solution{Suppose that the claim is false.  Let $S$ be the set of
positive integers $x$ for which there exist positive integers
$y$ and $z$ that solve the equation.  By assumption, $S$ is not empty.
Therefore, by the well-ordering principle, $S$ contains a smallest
element $x'$.  Let $y'$ and $z'$ be corresponding values of $y$ and
$z$ that give a solution.  By the preceding arguments, $x'$, $y'$, and
$z'$ must be even.  Thus $x'/2$, $y'/2$, and $z'/2$ are all positive
integers.  Dividing both sides of the original equation by $2^3$ shows
that these values also satisfy the equation. Therefore $x'/2$ is in $S$, contraditing the
definition of $x'$ as the smallest element of $S$.  Therefore, the
orginal supposition is wrong, and the claim is true.}

\end{problemparts}

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

\end{problems}
\end{document}
