\documentclass[12pt,oneside]{article}
\usepackage{light}

\showsolutions

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

\begin{document}

\generic{Quiz 1}{March 9, 2005}

\begin{center}
\textbf{YOUR NAME: } \underline{\hspace{3in}}
\end{center}

\textbf{Circle the name of your recitation instructor}:

\begin{center}
\begin{tabular}{c@{\hspace{0.5in}}c@{\hspace{0.5in}}c}
Ishan & Christos & Grant
\end{tabular}
\end{center}

\begin{itemize}

\item You may use one $8.5 \times 11$'' sheet with notes in you own
handwriting on both sides, but no other sources of information.

\item Calculators are not allowed.

\item You may assume all results from lecture, the notes, problem
sets, and recitation.

\item Write your solutions in the space provided.  If you
need more space, write on the back of the sheet containing the
problem.

\item Be neat and write legibly.  You will be graded not only on the
correctness of your answers, but also on the clarity with which you
express them.

\item The exam ends at 9:30 PM.

\item GOOD LUCK!

\end{itemize}

\vspace{0.25in}

\begin{center}
{\large
\begin{tabular}{|c|c|c|c|}
\hline
Problem & Points & Grade & Grader \\ \hline \hline
1 & 20 & & \\ \hline
2 & 15 & & \\ \hline
3 & 20 & & \\ \hline
4 & 15 & & \\ \hline
5 & 15 & & \\ \hline
6 & 15 & & \\ \hline
Total & 100 & & \\ \hline 
\end{tabular}
}
\end{center}

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

\newpage

\newcommand{\replies}{\Leftarrow}

\begin{problem}[20 points]

\bparts

\ppart Consider the proposition:
%
\[
R = \text{``For all $x \in S$, $P(x)$ implies $Q(x)$.''}
\]
%
For each statement below:
%
\begin{itemize}
\item If $R$ \textit{implies} that statement, then circle $\implies$.
\item If $R$ is \textit{implied by} that statement, then circle
$\replies$.
\end{itemize}
%
Thus, you might circle zero, one, or two arrows next to each
statement.  (Circle only implications that hold for \textit{all} sets
$S$ and \textit{all} predicates $P$ and $Q$.)
%
\vspace{0.35in}
%
\begin{center}
\begin{tabular}{c@{\hspace{0.35in}}c@{\hspace{0.35in}}l}

$\implies$ & $\replies$ & For all $x \in S$, $Q(x)$ implies $P(x)$. \\[0.35in]

\fbox{$\implies$} & \fbox{$\replies$} & For all $x \in S$, $\neg Q(x)$ implies $\neg P(x)$. \\[0.35in]

$\implies$ & \fbox{$\replies$} & For all $x \in S$, $P(x)$ and $Q(x)$. \\[0.35in]

\fbox{$\implies$} & \fbox{$\replies$} & There does not exist an $x \in S$ such that
not ($P(x)$ implies $Q(x)$). \\[0.35in]

$\implies$ & \fbox{$\replies$} & Pigs fly.

\end{tabular}
\end{center}

\newpage

\ppart Let $S$ be the set of all people, and let $M(x, y)$ be the
predicate, ``$x$ is the mother of $y$''.  Translate this proposition
into a clear English sentence involving no variables.
%
\[
\forall x\ (\neg \exists y\ (M(x, y) \wedge M(y, x)))
\]

\framebox[6in]{\insolutions{\parbox{5.5in}{``There are no two people
such that each is the mother of the other.''  Or, more simply, ``No
one is their own maternal grandmother.''}}\instatements{\rule{0in}{1.5in}}}

\vspace{0.5in}

\ppart Translate the following English sentence into logic notation
using the set $S$ and predicate $M$ defined above.
%
\begin{center}
``Everyone has a mother.''
\end{center}

\framebox[6in]{\insolutions{$\forall y\ \exists x\ M(x, y)$}
\instatements{\rule{0in}{1.5in}}}

\eparts

\end{problem}

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

\newpage

\begin{problem}[15 points]
Complete this proof that $n$ cents of postage can be formed using 3
and 5 cent stamps for all $n \geq 8$.

\begin{proof}  We use strong induction.

\bparts

\ppart Let $P(n)$ be the proposition that

\solution[\vspace{1in}]{$n$ cents of postage can be formed using 3 and
5 cent stamps.}

\ppart \textit{Base cases.}

\solution[\vspace{1.5in}]{$P(8)$, $P(9)$, and $P(10)$ are all true, since:
%
\begin{align*}
8 & = 5 + 3 \\
9 & = 3 + 3 + 3 \\
10 & = 5 + 5
\end{align*}
}

\ppart \textit{Inductive step.}

\solution[\vspace{3in}]{For $n \geq 10$, we assume $P(8)$, \ldots,
$P(n)$ and prove $P(n+1)$.  In particular, by assumption $P(n-2)$, we
can form $n-2$ cents of postage.  Adding a 3-cent stamp gives $n+1$
cents of postage, so $P(n+1)$ is true.}

\eparts

\noindent So $P(n)$ is true for all $n \geq 8$ by the principle of
strong induction.
\end{proof}
\end{problem}

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

\newpage

\begin{problem}[20 points]  Here is how to \term{tweak} an undirected graph:

\begin{enumerate}

\item Select distinct vertices $a$, $b$, $c$, and $d$ such that the
graph contains edges $\edge{a}{b}$ and $\edge{c}{d}$ and none of the
edges $\edge{a}{c}$, $\edge{a}{d}$, $\edge{b}{c}$, or $\edge{b}{d}$.
%
\begin{center}
\begin{picture}(88,88)(-8,-8)
\put(0,0){\line(0,1){72}}
\put(72,0){\line(0,1){72}}
\put(0,0){\circle*{8}}
\put(0,72){\circle*{8}}
\put(72,0){\circle*{8}}
\put(72,72){\circle*{8}}
\put(-16,72){\makebox(0,0){{\Large $a$}}}
\put(-16,0){\makebox(0,0){{\Large $b$}}}
\put(88,72){\makebox(0,0){{\Large $c$}}}
\put(88,0){\makebox(0,0){{\Large $d$}}}
\end{picture}
\end{center}

\item Delete edge $\edge{c}{d}$ and add edges $\edge{a}{c}$ and
$\edge{a}{d}$:
%
\begin{center}
\begin{picture}(88,88)(-8,-8)
\put(0,0){\line(0,1){72}}
\put(0,72){\line(1,-1){72}}
\put(0,72){\line(1,0){72}}
\put(0,0){\circle*{8}}
\put(0,72){\circle*{8}}
\put(72,0){\circle*{8}}
\put(72,72){\circle*{8}}
\put(-16,72){\makebox(0,0){{\Large $a$}}}
\put(-16,0){\makebox(0,0){{\Large $b$}}}
\put(88,72){\makebox(0,0){{\Large $c$}}}
\put(88,0){\makebox(0,0){{\Large $d$}}}
\end{picture}
\end{center}


\end{enumerate}

\bparts

\ppart In the box on the right, draw a graph that can be
obtained by tweaking the graph on the left.
%
\begin{center}
\begin{picture}(408,192)(-24,-32)
%\put(-24,-32){\dashbox(408,192){}} % bounding box
\put(0,32){\line(0,1){64}}
\put(128,32){\line(0,1){64}}
\put(64,0){\line(-2,1){64}}
\put(64,0){\line(2,1){64}}
\put(64,128){\line(-2,-1){64}}
\put(64,128){\line(2,-1){64}}
\put(0,32){\circle*{8}}
\put(0,96){\circle*{8}}
\put(64,0){\circle*{8}}
\put(64,128){\circle*{8}}
\put(128,32){\circle*{8}}
\put(128,96){\circle*{8}}
\put(64,140){\makebox(0,0){{\Large $1$}}}
\put(140,96){\makebox(0,0){{\Large $2$}}}
\put(140,32){\makebox(0,0){{\Large $3$}}}
\put(64,-12){\makebox(0,0){{\Large $4$}}}
\put(-12,32){\makebox(0,0){{\Large $5$}}}
\put(-12,96){\makebox(0,0){{\Large $6$}}}
\put(160,64){\makebox(0,0){{\Huge $\rightarrow$}}}
\put(192,-32){\framebox(192,192){}}
\insolutions{
\put(224,32){\line(0,1){64}}
\put(224,96){\line(1,0){128}}
\put(224,96){\line(2,-1){128}}
%\put(352,32){\line(0,1){64}}
\put(288,0){\line(-2,1){64}}
\put(288,0){\line(2,1){64}}
\put(288,128){\line(-2,-1){64}}
\put(288,128){\line(2,-1){64}}
\put(224,32){\circle*{8}}
\put(224,96){\circle*{8}}
\put(288,0){\circle*{8}}
\put(288,128){\circle*{8}}
\put(352,32){\circle*{8}}
\put(352,96){\circle*{8}}
\put(288,140){\makebox(0,0){{\Large $1$}}}
\put(364,96){\makebox(0,0){{\Large $2$}}}
\put(364,32){\makebox(0,0){{\Large $3$}}}
\put(288,-12){\makebox(0,0){{\Large $4$}}}
\put(212,32){\makebox(0,0){{\Large $5$}}}
\put(212,96){\makebox(0,0){{\Large $6$}}}}
\end{picture}
\end{center}

\newpage

\ppart Suppose that $G_0$ is an undirected graph with an Euler tour.
Also, suppose $G_1$ is obtained by tweaking $G_0$, $G_2$ by tweaking
$G_1$, and so forth.  Use induction to prove that every graph $G_n$
obtainable in this way has an Euler tour.

For your reference:
%
\begin{itemize}
\item An \term{Euler tour} is a closed walk that traverses every edge
in a graph exactly once.
\item A graph is \term{connected} if and only if there is a path
between every pair of vertices.
\item \textbf{Theorem. }  An undirected graph has an Euler tour if and only if the
graph is connected and every vertex has even degree.

\end{itemize}

\solution{We use induction.  Let $P(n)$ be the proposition that $G_n$
has an Euler tour.

\noindent \textit{Base case.}  $G_0$ has an Euler tour by supposition.

\noindent \textit{Inductive step.}  For $n \geq 0$, we assume $G_n$
has an Euler Tour and prove that $G_{n+1}$ also has an Euler tour.
Specifically, we show that $G_{n+1}$ has only even-degree vertices and
is connected:
%
\begin{itemize}

\item Every vertex in $G_n$ has even degree, since $G_n$ has an Euler
tour.  Every vertex in $G_{n+1}$ has the same degree, except for
vertex $a$ which has degree two greater.  Thus, every vertex in
$G_{n+1}$ also has even degree.

\item Consider arbitrary vertices $u$ and $v$.  Since $G_n$ is
connected, there is a path from $u$ to $v$ in $G_n$.  If the path does
not contain $\edge{c}{d}$, then the same path exists in $G_{n+1}$.  If
the path does contain $\edge{c}{d}$, then there is a corresponding
path in $G_{n+1}$ where $\edge{c}{d}$ is replaced by edges
$\edge{c}{a}$ and $\edge{a}{d}$.  Thus, there is a path between every
pair of vertices in $G_{n+1}$, which means that $G_{n+1}$ is
connected.

\end{itemize}

These two facts imply $G_{n+1}$ has an Euler tour.  By induction,
every graph $G_n$ obtainable by repeatedly tweaking $G_0$ has an Euler
tour.}

\eparts

\end{problem}

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

\newpage

\newcommand{\mybox}[1]{\fbox{\rule{0in}{0.15in}{\instatements{\hspace{0.25in}}\insolutions{#1}}}}

\begin{problem}[15 points]  Fill in the boxes below.  All variables denote
integers.  No explanations are required, but we can only award partial
credit for an incorrect answer if you show your reasoning.

\bparts

\ppart Suppose $x$ is a multiple of 17.  Write the smallest
\textbf{nonnegative} integers that make this statement true.

{\Large
\[
2 x^{32} - 6 x^{17} + 4 x^{16} - 4 x + 6 \equiv \mybox{0} \cdot x + \mybox{6} \pmod{17}
\]
}

\solution[\vspace{1in}]{If $x$ is a multiple of $17$, then $x \equiv 0
\pmod{17}$.  Therefore, all terms involving $x$ on the left are
congruent to zero.}

\ppart Now suppose $x$ is \textit{not} a multiple of 17.  Write the
smallest \textbf{nonnegative} integers that make this statement true.

{\Large
\[
2 x^{32} - 6 x^{17} + 4 x^{16} - 4 x + 6 \equiv \mybox{7} \cdot x + \mybox{12} \pmod{17}
\]
}

\solution[\vspace{1in}]{By Fermat's Theorem, $x^{16} \equiv 1
\pmod{17}$.  Thus, we can reason as follows:
%
\begin{align*}
2 x^{32} - 6 x^{17} + 4 x^{16} - 4 x + 6
  & \equiv 2 \paren{x^{16}}^2 - 6 x \paren{x^{16}} + 4 x^{16} - 4 x + 6 \pmod{17} \\
  & \equiv 2 - 6 x + 4 - 4x + 6 \pmod{17} \\
  & \equiv -10x + 12 \pmod{17} \\
  & \equiv 7 x + 12 \pmod{17}
\end{align*}
}

\ppart In the box, write the smallest \textbf{positive} integer that
makes this statement true:

There exist integers $s$ and $t$ such that
%
{\Large
\[
s \cdot 117 + t \cdot 153 = x
\]}
%
if and only if
%
{\Large
\[
x \equiv 0 \pmod{\mybox{9}}
\]}

\solution{Recall that an integer $x$ is expressible as a linear
combination of $a$ and $b$ if and only if $x$ is a multiple of
$\gcd(a, b)$, i.e. $x \equiv 0 \pmod{\gcd(a, b)}$.  In this case,
Euclid's algorithm gives:
%
\[
\gcd(153, 117) = \gcd(117, 36) = \gcd(36, 9) = 9
\]
}

\eparts

\end{problem}

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

\newpage

\begin{problem}[15 points]
Let $p$, $q$, and $r$ be distinct primes.  Prove that there exist
integers $a$, $b$, and $c$ such that:
%
\[
a \cdot (p q) + b \cdot (q r) + c \cdot (r p) = 1
\]
%
\begin{center}
(Hint:  First, consider linear combinations of just $pq$ and $qr$.)
\end{center}
\end{problem}

\solution{Since $\gcd(pq, qr) = q$, there exist integers $s$ and $t$
such that:
%
\[
s (p q) + t (q r) = q
\]
%
Now $\gcd(q, r p) = 1$, so there exist integers $u$ and $v$ such that:
%
\[
u q + v (r p) = 1
\]
%
Therefore:
%
\[
u (s (p q) + t (q r)) + v (r p) = (u s) (p q) + (u t) (q r) + v (r p) = 1
\]
%
Let $a = u s$, $b = u t$, and $c = v$.
}

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

\newpage

\begin{problem}[15 points]
In a chicken tournament, for every pair of chickens $u$ and $v$,
either $u$ pecks $v$ or $v$ pecks $u$, but not both.  A \textit{king}
is a chicken $u$ such that for every other chicken $v$, either
%
\begin{itemize}
\item $u$ pecks $v$, or
\item $u$ pecks a chicken $w$ and $w$ pecks $v$.
\end{itemize}
%
Complete the proof of the following theorem.

\begin{theorem*}
If chicken $c$ is pecked, then $c$ is pecked by a king.
\end{theorem*}

\begin{proof}
Let $S_c$ be the set of all chickens pecked by $c$, and let $D_c$ be
the set of all chickens that peck $c$.  The situation is illustrated
below:
%
\begin{center}
\rotatebox{-90}{\includegraphics{pecking-order}}
\end{center}
%
\begin{center}
(Hint: Apply the King Chicken Theorem to $D_c$.)
\end{center}
%
\instatements{\vspace{4in}} \insolutions{If chicken $c$ is pecked,
then the set $D_c$ is nonempty.  Thus, there is a mini-tournament
among the chickens in $D_c$, which has a king $d$ by the King Chicken
Theorem.  We will show that $d$ is actually a king of the entire
tournament.
%
\begin{itemize}
\item $d$ pecks every chicken in $D_c$ (directly or indirectly), since
it is a king of $D_c$.
\item $d$ pecks chicken $c$ directly, since $d$ is in $D_c$.
\item $d$ pecks every chicken in $S_c$ indirectly, since it pecks $c$
and $c$ pecks every chicken in $S_c$.
\end{itemize}
%
Thus, $c$ is pecked by a king; namely, $d$.
}
\end{proof}

\end{problem}

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

\end{document}
