\documentclass[12pt]{article}
\usepackage{latex-macros/course}% !! use the macros

\instatements{
\renewcommand{\exampreamble}{	% !! renew \exampreamble 
  \textbf{Circle the name of your Tutorial Instructor}:
  \begin{center}
  \renewcommand{\arraystretch}{1.5}
  \begin{tabular}{cccc}
  David    & Hanson   & Jelani & Sayan
  \end{tabular}
  \end{center}
  \begin{itemize}

  \item 
  This quiz is \textbf{closed book} except for a personal one-page crib
  sheet.  You may assume any of the results presented in class or in the
  lecture notes.  Total time is 80 minutes. 

  \item 
  There are seven (7) problems totaling 100 points.  
  Problems are labeled with their point values.

  \item 
  Write your solutions in the space provided.  If you need more
  space, write on the back of the sheet containing the problem.
  Please keep your entire answer to a problem on that problem's page.

\iffalse
  \item  
  \textbf{Be neat and write legibly}.  You will be graded not only on
  the correctness of your answer, but also on the clarity with which
  you express it.
\fi

  \item 
  GOOD LUCK!
  \end{itemize}}
}

\begin{document}
\quiz{1}

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

%\instatements{\newpage}

\begin{examproblem}{15}
Let $G$ be an undirected graph.  Let $P(x, y)$ mean that there is a path
from vertex $x$ to vertex $y$.  Express each of the following sentences in
terms of $P$, quantifiers, logical connectives, and equality, using
variables that range over the vertices of $G$.  (Reminder: there is a
zero-length path from any vertex to itself.)

\bparts

\ppart[3] Vertices $x$ and $y$ are in the same connected component.

\solution[\vspace{0.75in}]{
$P(x,y)$}

\ppart[3] $G$ has a vertex of degree zero.  (Reminder: undirected graphs
only have edges between distinct vertices, that is, no self-loops.)

\solution[\vspace{0.75in}]{$\exists x \forall y.\, P(x,y) \implies x = y$.}

\ppart[4] $G$ has at least three connected components.

\solution[\vspace{0.75in}]{
\[
\exists x,y,z.\, \neg P(x,y) \land \neg P(x,z) \land \neg P(y,z).
\]
}

\ppart[5] There is a positive-length \emph{simple} path from $x$ to $y$.

\solution[\vspace{0.75in}]{There is a positive length simple path between
two vertices iff the vertices are distinct and there is a path between
them, so we can express this as
\[
x \neq y \land P(x,y).
\]}

\eparts
\end{examproblem}

\iffalse

\begin{examproblem}{15}
For each of the following logical formulas, fill in the boxes with $\true$
or $\false$ to indicate whether the formula is true when the domain of
discourse is
\begin{itemize}
\item $\rationals$, the rationals,
\item $\integers_5$, the integers modulo 5 (with ``='' interpreted as $\equiv
  \pmod 5$), and similarly,
\item $\integers_6$, the integers modulo 6.
\end{itemize}

{\large
\[
\begin{array}{|l|l|l|l|}
Statement & \rationals & \integers_5 & \integers_6\\
\hline
\forall x \exists y.\ x^2 = y &&&\\
\hline
\forall y \exists x.\ x^2=y &&&\\
\hline
\forall x \neq 0\, \exists y.\ xy=1 &&&\\
\hline
\forall x.\, 3x = 0  \implies x = 0 &&&\\
\hline
\end{array}
\]
}

\solution{
\[
\begin{array}{l|l|l|l|}
Statement & \rationals & \integers_5 & \integers_6\\
\hline
\forall x \exists y\ (x^2 = y) & \true & \true & \true\\
\hline
\forall y \exists x\ (x^2=y)  & \false & \mbox{2pts } \false & \mbox{2pts } \false\\
\hline
\forall x\neq 0\, \exists y\ (xy=1) & \true & \true\ (5\text{ is prime}) &
\mbox{2pts } \false\ (\text{2 has no inverse})\\
\hline
\forall x.\, 3x = 0  \implies x = 0 & \true & \true & \false \\
\hline
\end{array}
\]
}
\end{examproblem}
\fi

\instatements{\newpage}

\begin{examproblem}{10} Classify each of the following binary relations as
\begin{enumerate}
\item[E:] An equivalence relation.
\item[T:] A Total order,
\item[P:] A Partial order that is not total.
\item[S:] A Symmetric relation that is not transitive.
\item[N:] None of the above.
\end{enumerate}

%This is a multiple choice problem: do not explain your answer.

\bparts

\ppart[2] The relation between times during a single day: $x$ and $y$
are at most twenty minutes apart. \brule{2em}

\solution{\textbf{S}: This relation is obviously symmetric.  It is
not transitive:
{\footnotesize 1:00}$R\,${\footnotesize 1:15}, and
{\footnotesize 1:15}$R\,${\footnotesize 1:22}, but 
$\neg\paren{\text{{\footnotesize 1:00}}R\,\text{{\footnotesize 1:22}}}$.}

\ppart[2] The relation between times during a single day: $x$ is
more than twenty minutes later than $y$. \brule{2em}

\solution{\textbf{P}: This relation is asymmetric and transitive.  It is
not a total ordering because some times are incomparable to each other.
For example, {\footnotesize 1:15} is incomparable to {\footnotesize
1:22}.}

\ppart[2] The relation between vertices in an arbitrary digraph: there is
a path from $v$ to $w$.  \brule{2em}

\solution{\textbf{N}: This relation is transitive but won't be a partial
order unless the graph is acyclic.}

\ppart[2] The relation between vertices in an undirected graph: there
is a path from $v$ to $w$.  \brule{2em}

\solution{\textbf{E}: In fact, the connected components of the graph are
the equivalence classes of this relation.}

\ppart[2] The relation between Fall '05 6.042 students: student $s$ is
older but also shorter than $t$. \brule{2em}

\solution{\textbf{P}: This relation is the product of the ``older than''
and the ``shorter than'' orders, and so is a partial order.  It is not
total because there is a younger student who is taller than an older
student.}

\eparts
\end{examproblem}


\instatements{\newpage}

\begin{examproblem}{20}
% Strong Induction

Let $G_0=1$, $G_1=2$, $G_2=4$, and define
\begin{equation}\label{Pn}
G_n \eqdef  G_{n-1} +2G_{n-2} + G_{n-3}
\end{equation}
for $n \geq 3$.  Show by induction that $G_n\leq \paren{2.2}^n$ for all $n \geq
0$.

\solution{

The proof is by strong induction with hypothesis $P(n) := G_n\leq \paren{2.2}^n$.

\begin{proof}
\textbf{Base Cases}

\textbf{$n=0$:} $G_0 \eqdef 1 = \paren{2.2}^0$.

\textbf{$n=1$:} $G_1 \eqdef 2 < 2.2 = \paren{2.2}^1$.

\textbf{$n=2$:} $G_2 \eqdef 4 < 4.84 = \paren{2.2}^2$.

\textbf{Inductive Step}:
Assume $n \geq 2$ and $P(k)$ for all $k$ such that $0 \leq k \leq n$.
\begin{align*}
G_{n+1}
& \eqdef G_n +2G_{n-1} + G_{n-2} & \text{by~\eqref{Pn}}\\
& \leq (2.2)^n + 2(2.2)^{n-1} + (2.2)^{n-2} & \text{by induction hypothesis}\\
& = (2.2)^{n-2} [(2.2)^2 + 2(2.2) + 1]\\
& = (2.2)^{n-2} [(2.2 + 1)^2]\\
& = (2.2)^{n-2} (3.2)^2\\
& = (2.2)^{n-2} (10.24)\\
& < (2.2)^{n-2} (10.648)\\
& = (2.2)^{n-2} (2.2)^3\\
& = (2.2)^{n+1}
\end{align*}
\end{proof}

\iffalse
One common error in this proof was not doing the proper base cases.
Students also had problems using the strong inductive assumptions.  Note
that points were also deducted for not adequately showing that
$(3.2)^2<(2.2)^3$.
\fi
}

\end{examproblem}

\instatements{\newpage}

\begin{examproblem}{20}

An \emph{intersection graph} is an undirected graph whose vertices are
sets and whose edges are specified by the rule that there is an edge between
vertices $A$ and $B$ iff $A \neq B$ and $A \intersect B \neq \emptyset$.

\bparts

\ppart[1] \label{ig} Draw the intersection graph whose vertices are the
sets
\[
\set{1,2,3},
\set{1,9,10},
\set{2,4,6,8,10},
\set{3,4,5},
\set{5,6,7},
\set{7,8,9}
\]

\solution[\vspace{2in}]{
\mfigure{!}{1.5in}{figures/W5.pdf}
}

\ppart[3] What is the chromatic number of the graph in part~\eqref{ig}?
\brule{0.3in}

\solution{4.  The graph is isomorphic to the wheel, $W_5$.  All wheels with
an odd-length rim have chromatic number 4, as explained in lecture.}

\ppart[3] \iffalse A graph is $k$-connected if it remains connected after
any set of $k-1$ edges are removed.\fi  What is the largest $k$ such that
the graph in part~\eqref{ig} is $k$-connected? \brule{0.3in} \solution{3.}
\eparts

We now consider an arbitrary undirected graph, $G$.  For any vertex, $v$,
of $G$, let $I(v)$ be the set of edges incident to $v$.

\bparts

\ppart[3]\label{dIv} Explain how to uniquely determine the vertex $v$
given any two edges in $I(v)$.

\solution[\vspace{0.5in}]{Just find a vertex that the two edges have in
common.  This must be $v$.}

\instatements{\newpage}

\ppart[10] An \emph{incidence-set} is the set of edges incident to some
vertex, that is, a set equal to $I(v)$ for some vertex $v$ of $G$.  Prove
that if $G$ is a graph whose vertices all have degree greater than 1, then
the function, $I$, is an isomorphism between $G$ and the intersection
graph whose vertices are the incidence-sets of $G$.

\solution[\newpage]{ Let $H$ be the intersection graph whose vertices are
the incidence-sets of $G$.  By definition of $H$, the function, $I$, is a
surjection onto the vertices of $H$.  Moreover, since each incidence-set
contains at least two edges, part~\eqref{dIv} implies that given $I(v)$,
we can uniquely determine $v$.  This means $I$ is also an injection into
the vertices of $H$, and therefore is a bijection from the vertices of $G$
to the vertices of $H$.  Also
\begin{align*}
\edge{v}{w} \text{ is an edge of } G
 & \qiff [\edge{v}{w} \in I(v) \text{ and } \edge{v}{w} \in I(w)]\\
 & \qiff v \neq w \text{ and } I(v) \intersect I(w) \neq \emptyset\\
 & \qiff \edge{I(v)}{I(w)} \text{ is an edge of } H,
\end{align*}
which proves that $I$ is an isomorphism.

Incidentally, if $G$ happens to have any vertices of degree $< 2$, then
it's easy to assign special sets to these vertices in such a way that
these special sets, along with the incidence sets of vertices of degree
$\geq 2$, are the vertices of an intersection graph that is isomorphic to
$G$.  This shows that \emph{every} undirected graph is isomorphic to an
intersection graph.}

\eparts
\end{examproblem}


\instatements{\newpage}


\begin{examproblem}{10}
Two banks only allow transactions that are multiples of $3^9$ dollars or
$5^7$ dollars.  Is there a series of transactions whose net result is a
payment of 1 dollar from the first bank to the second bank?  Briefly
explain why or why not.

\solution[\vspace{3in}]{
Yes.  Since $3^9$ and $5^7$ have no common prime factors, their gcd is 1,
and so there are positive integers $s,t$ such that $s\paren{3^9} -
t\paren{5^7} = 1$.  So the first bank should pay the second bank $3^9$
dollars $s$ times, and accept payment of $5^7$ dollars form the second
bank $t$ times for a net transfer of 1 dollar to the second bank.
}


\iffalse

What is the remainder of $3^{4001}$ divided by 40? \brule{0.7in}

\solution[\vspace{2in}]{
3.

Note that $3^4 = 81 \equiv 1 \pmod{40}$.   So for $n$ divisible by 4, we
have
\[
3^n = \paren{3^4}^{n/4} \equiv 1^{n/4} \equiv 1 \pmod{40}.
\]
Therefore,
\[
3^{4001} = 3^{4000} \cdot 3 \equiv 1 \cdot 3 \equiv 3 \pmod{40}.
\]
}\fi


\end{examproblem}

%S04 q1

\begin{examproblem}{15}
Each year, Santa's reindeer hold ``Reindeer Games'', from which
Rudolph is pointedly excluded.  The Games consist of a sequence of
matches, where one reindeer competes against another.  Draws are not
possible.

On Christmas Eve, Santa produces a rank list of all his reindeer.  If
reindeer $p$ lost a match to reindeer $q$, then $p$ appears below $q$ in
Santa's ranking, but if he has any choice because of unplayed matches,
Santa can give higher rank to the reindeer he likes better.  To prevent
confusion, two reindeer may not play a match if either outcome would lead
to a cycle of reindeer, where each lost to the next.

\iffalse
Here is an example of a cycle:
\mfigure{!}{1.75in}{figures/cycle}
\fi

Though it is only October, the 2004 Reindeer Games have already begun.  We
can describe the results so far with a binary relation, $L$, on the set of
reindeer, where $p L q$ means that reindeer $p$ lost a match to reindeer
$q$.  Let $L^+$ be the corresponding positive-length path
relation\footnote{Thus, reindeer $p$ is related to reindeer $q$ by $L^+$
if $p$ lost to $q$ or if $p$ lost to a reindeer who lost to $q$ or if $p$
lost to a reindeer who lost to a reindeer who lost to $q$, etc.}.  Note
that $L^+$ is a partial order, so we can regard a match loser as
``smaller'' than the winner.

\bigskip

On the following page you'll find a list of terms and a sequence of
statements.  Add the appropriate term to each statement.

\newpage

\begin{center}
\textbf{Terms}

\begin{tabular}{lll}
 a strict partial order  & a weak partial order   & a total order\\
 comparable elements     & incomparable elements  & a chain\\
 an antichain            & a maximal antichain    & a topological sort\\
 a minimum element       & a minimal element\\
 a maximum element       & a maximal element
\end{tabular}
\end{center}

\centerline{\textbf{Statements}}

\bparts

\ppart[1] An unbeaten reindeer is

\brule{3in} of the partial order $L^+$. \solution{a maximal element}

\ppart[1] A reindeer who has lost every match so far is

\brule{3in} of the partial order $L^+$. \solution{a minimal element}

\ppart[1] Two reindeer can \emph{not} play a match if they are

\brule{3in} of $L^+$. \solution{comparable elements}

\ppart[1] A reindeer assured of first place in Santa's ranking is

\brule{3in} of $L^+$. \solution{a maximum element}

\ppart[1] A sequence of reindeer which \emph{must} appear in the same
order in Santa's rank list is

\brule{3in}. \solution{a chain}

\ppart[2] A set of reindeer such that any two could still play a match
is

\brule{3in}. \solution{an antichain}

\ppart[2] The fact that no reindeer loses a match to himself implies
that $L^+$ is

\brule{3in}.  \solution{a strict partial order}

\ppart[2] Santa's final ranking of his reindeer on Christmas Eve must be

\brule{3in} of $L^+$.  \solution{a topological sort}

\ppart[2] No more matches are possible if and only if $L^+$ is

\brule{3in}.  \solution{a total order}

\ppart[2] Suppose that Santa has 11 reindeer.  If no more matches can
be played, what is the smallest possible number of matches already
played?  \brule{0.3in}

\solution{10.

Call the reindeer $r_1, \dots, r_{11}$.  Then no more matches can be
played if $r_1$ lost to $r_2$, $r_2$ lost to $r_3$, etc.  If only ten
matches have been played, then the corresponding digraph will not even be
connected if we regard the edges as undirected.  So there would be two
disjoint sets of reindeer, $S$ and $T$, such that no reindeer in $S$ has
played a match against a reindeer in $T$.  Therefore, more matches can be
played; in particular, any reindeer in $S$ can play against any reindeer
in $T$.}

\eparts

\end{examproblem}


\instatements{\newpage}
\begin{examproblem}{10}

A \emph{map} is a connected planar graph with a planar drawing whose face
boundaries are simple cycles.

\bparts

\ppart[7] Prove that if a map has no simple cycle of length 3, then
\begin{equation}\label{2v}
e \leq 2v -4,
\end{equation}
where $v$ is the number of vertices and $e$ is the number of edges in the
graph.

\solution[\vspace{3in}]{
Since there is no simple cycle of length 3 and face boundaries are simple
cycles, every face must be of length 4 or more.  We know that in a planar
drawing, each edge appears twice on the face boundaries, so
\begin{equation}\label{4f}
2e = \sum_{b \in\text{ boundaries}} \text{length}(b) \geq \paren{\sum_{b
  \in\text{ boundaries}} 4} = 4f,
\end{equation}
where $f$ is the number of faces.  By Euler's formula, $f = e-v+2$, so
substituting for $f$ in~\eqref{4f}, yields
\[
2e \geq 4(e-v+2),
\]
which simplifies to~\eqref{2v}.
}

\ppart[3] Prove that $K_{3,3}$ is not a map.  ($K_{3,3}$ is the graph
with six vertices and an edge from each of the first three vertices to
each of the last three.)

\solution[\vspace{2.5in}]{ $K_{3,3}$ is by definition bipartite, and hence
has no odd-length simple cycle, and in particular, no length 3 cycle.
(This could also be checked exhaustively.)  \iffalse Also, there is a path
of length two between every pair of nonadjacent vertices, and so it is
obviously connected.\fi

However, it has 9 edges and 6 vertices, and since $9 > 8 = 2 \cdot 6 - 4$,
it does not satisfy~\eqref{2v}, and so cannot be a map.

Incidentally, this implies that $K_{3,3}$ is not planar.  The reason is
that connected planar graphs which are not maps are the ones with
``dongles'' or ``crossbars,'' as explained in lecture.  But all edges in
dongles and crossbars are cut edges.  So a connected graph like $K_{3,3}$
with no cut edges is planar iff it is a map.}

\eparts

\end{examproblem}



\end{document}
