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

%\backwardscompatibility	% !! use for backwards compatibility
%\showsolutions	 		% !! use to force solutions & skip query
%\hidesolutions			% !! use to force no solutions & skip query


\def\brule#1{\instatements{\enskip\vrule width#1 height -1.1pt depth 1.5pt\relax}}

\ifshowsolutions
{}
\else
\renewcommand{\exampreamble}{	% !! renew \exampreamble 
  \textbf{Circle the name of your Tutorial Instructor}:
  \begin{center}
  \renewcommand{\arraystretch}{1.5}
  \begin{tabular}{llllllll}
  Adrian & Georgi & Josh  & Karen & Lee & Min  & Nikos & Tina   
  \end{tabular}
  \end{center}
  \begin{itemize}
  \item 
  This quiz is \textbf{closed book}. There is an Appendix 
  with standard definitions.
  \item 
  There are five (5) problems totaling 100 points. Total time is 110 minutes. 
  %% Problems are labeled with their point values.
  \item 
  Put your name on the top of {\bf every} page -- \emph{these
  pages may be separated for grading}.
  \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.
  \item 
  You may assume any of the results presented in class or in the
  lecture notes.
  \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.
  \item 
  GOOD LUCK!
  \end{itemize}}
\fi

\begin{document} 
\quiz{1}			% !! start the paper


% {\bf TOPICS:
% \begin{enumerate}
% \item Logic, Proof Methods
% \item Induction, Strong Induction
% \item Relations (Equivalence, Partial Orders, Paths)
% \item Graphs (Coloring, Connectivity, Paths)
% \item Computational Processes (State Machines, Invariants,
% Termination)
% \end{enumerate}

%% NEWPAGE--------------------------------------------------
\ifshowsolutions {} \else \newpage \fi

\begin{examproblem}{20}

We ask you to construct some logical formulas using only propositional
formulas and quantification of variables which range over just one domain
of discourse, $D$, starting from formulas only of the forms $x=y$ and
$P(x,y)$.  Here $x$ and $y$ may be replaced by any variables, but $P$ is a
fixed symbol.

For example, a formula of this kind asserting that $P$ is the identity
relation is
\[
\forall x \forall y\ P(x,y) \iff x = y.
\]

\bparts

\ppart[10] An interpretation for the binary predicate symbol $P$ may be
any binary relation on $D$.  Write a formula whose meaning is that the
interpretation of $P$ is an equivalence relation on $D$.

\solution{

$\forall x P(x,x) \wedge \forall x\forall y (P(x,y) \implies P(y,x))
 \wedge \forall x\forall y \forall z[(P(x,y) \wedge P(y,z)) \implies
P(x,z)]$.
}

\ppart[10] We can use any simple graph, $G$, to interpret a formula by
letting $D$ be the set of vertices of $G$ and letting $P(x,y)$ mean there
is an edge between $x$ and $y$.  For example, the formula
\[
\forall x \forall y P(x,y)
\]
is true exactly when $G$ is a complete graph.  On the
other hand, the formula
\[
\exists x \exists y (P(x,y) \wedge \neg P(y,x))
\]
is not true for \emph{any} simple graph because in simple graphs edges are
undirected, so an edge between $x$ and $y$ is also and edge between $y$ and
$x$.

Write a formula which is not true for any \emph{two-colorable} graph, but
is true for some simple graph.  (Two-colorable graphs the same as bipartite
graphs.)  Briefly explain why your formula has this property.

\solution{
Say that the graph has a three cycle.  This is satisfied by any graph with
such a cycle, but a three cycle prevents two-colorability.
\[
\begin{array}{lr}
\exists x,y,z(\neg(x=y \vee x =z \vee y=z) & \mbox{$x, y$ and $z$ are three
different vertices}\\
\wedge P(x,y) \wedge P(y,z) \wedge P(z,x)). & \mbox{they form a 3-cycle}
\end{array}
\]
}

\eparts
\end{examproblem}


%% NEWPAGE--------------------------------------------------
\ifshowsolutions {} \else \newpage \fi

\begin{examproblem}{20}
To encourage collaborative study, the 6.042 staff is considering assigning
each student to a study group with two or three other students.  Prove that
as long as the enrollment is large enough, the class can always be divided
into such study groups.

\solution{\begin{proof} The proof is by strong induction.  The induction
hypothesis is that a class with $n \geq 6$ students can be divided into
teams of 3 or 4.  More precisely
\[
P(n) \eqdef\quad  n\geq 6 \implies \exists x,y \in \naturals\ 3x+4y = n.
\]

For any $n \geq 0$, we may assume $P(6), \dots, P(n-1)$ to prove $P(n)$.

\textbf{Case 1:} ($n <6$).  $P(n)$ holds because the hypothesis $n \geq 6$
is false.

\textbf{Case 2:} ($n=6,7,\text{ or }8$) $P(6)$ is true because there could
be two teams of 3, $P(7)$ is true because there could be a team of 3 and a
team of 4, and $P(8)$ is true because there could be two teams of 4.

\textbf{Case 3:} ($n \geq 9$).  Of course $n> n-3$ so
$P(n-3)$ holds by the strong induction hypothesis.  But $n-3 \geq 6$, so
$P(n-3)$ implies $3x'+4y' = n-3$ for
some $x',y'\in\naturals$, and therefore $3x+4y=n$ where $x\eqdef x'+1$
and $y \eqdef y'$.  So $P(n)$ holds, as required.
\end{proof}}
\end{examproblem}


%% NEWPAGE--------------------------------------------------
\ifshowsolutions {} \else \newpage \fi

\begin{examproblem}{15}  % Fall 2000, practice quiz, revised to be in better taste

Students are planning a campaign against MIT's requirement that they join
the meal plan.  This involves a number of tasks, each of which takes one
day to complete.  Some tasks cannot be started until other prerequisite
tasks are complete.  The tasks and their prerequisites are listed below.

\begin{center}
\begin{tabular}{cll}
\textsc{Abbrv.} & \textsc{Task} & \textsc{Prerequisites} \\
C & Cook for themselves & \\
N & Notify Chuck & B \\
D & Signal the Free Food Daemons & B \\
B & Blow the trumpet & \\
T & Sell T-shirts: ``Where do you want to eat today?'' &
N \\
Q & Take the 6.042 quiz & S \\
G & Go to Campus Dining Review meeting & D,N \\
S & Suppress Aramark and condescending admins & C,N 
\end{tabular}
\end{center}

\begin{problemparts}

\ppart[7] Represent the tasks and their prerequisites as a
directed graph.  

\solution{
\centerline{\includegraphics[height=2.5in]{figures/death}}
%\centerline{\psfig{figure=/a/class/6.042/fall00/handouts/figures/death.eps,height=2.5in}}
}

\ifshowsolutions
{}
\else
\vspace{2.5in}
\fi


\ppart[8] So many MIT students are unhappy with the meal plan that
finding students to work on several tasks at once is no problem.  For
example, if there were no prerequisites, students could do all the tasks
in parallel, and the campaign could be completed in one day --- even
though it would not be a good idea to blow the trumpet during the 6.042
Quiz \texttt{:-)}

In this situation, what is the minimum number of days needed to complete
the campaign against the meal plan?  Briefly explain why.

\solution{
The minimum required time is 4 (length of the critical path B-N-S-Q).
}

\ifshowsolutions
{}
\else
\vspace{1.5in}
\fi

\end{problemparts}

\end{examproblem}




%% NEWPAGE--------------------------------------------------
\ifshowsolutions {} \else \newpage \fi

\begin{examproblem}{25}
We apply the following operation to a simple graph $G$:
pick two vertices $u \neq v$ such that either
\begin{enumerate}
\item there is an edge of $G$ between $u$ and $v$ and there is also a path
from $u$ to $v$ which does \emph{not} include this edge; in this case,
delete the edge $\set{u,v}$.

\item there is no path from $u$ to $v$; in this case, add the edge
$\set{u,v}$.
\end{enumerate}

Keep repeating these operations until it is no longer possible to find two
vertices $u \neq v$ to which an operation applies.

Assume the vertices of $G$ are the integers $1,2,\dots,n$ for some $n \geq
2$.  This procedure can be modelled as a state machine whose states are
all possible simple graphs with vertices $1,2,\dots,n$.  $G$ is the start
state, and the final states are the graphs on which no operation is
possible.

\bparts

\ppart[4] Let $G$ be the graph with vertices $\set{1,2,3,4}$ and edges
\[
\set{\set{1,2},\set{3,4}}
\]
What are the possible final states reachable from start state $G$?  Draw
them.

\solution{It's not possible to delete any edge.  The procedure can only
add an edge connecting exactly one of vertices 1 or 2 to exactly one of
vertices 3 or 4, and then terminate.  So there are four possible final
states}

\ppart[9] \label{derived} Below are three derived variables.  Indicate the
\emph{strongest} property from the list below that each variable is
guaranteed to satisfy, no matter what the starting graph $G$ is, and
justify your answer.  The properties are: \emph{constant}, \emph{strictly
increasing}, \emph{strictly decreasing} ,\emph{weakly increasing},
\emph{weakly decreasing}, \emph{none of these}

For any state, let $e$ be the number of edges in it, and let $c$ be the
number of connected components it has.  For example, since $e$ may
increase or decrease in a transition, it does not have any of the first
four properties, so it would be classified \emph{none of these}.  The
derived variables are
\begin{enumerate}

\item[i)] $c$, \solution{weakly decreasing}
\item[ii)] $c+e$, \solution{weakly decreasing}
\item[iii)] $2c+e$. \solution{strictly decreasing}

\end{enumerate}

\ppart[4] Conclude that the procedure terminates.

\solution{Because the derived variable iii) is a natural-number valued
variable and is decreasing.

To show that the variable iii) decreases, note that the rule for deleting
an edge ensures that the connectedness relation does not change, so
neither does the number of connected components; therefore the variable
decreases by one when an edge is deleted.  The rule for adding an edge
ensures that the number of connected components decreases by one, so the
variable changes by $-2$ for the reduced number of components and $+1$ for
the added edge, for a net decrease of 1.}

\ppart[8] Prove that any final state must be a 
tree on the vertices.

\solution{We use the characterization of a tree as a cycle-free,
connected, simple graph.

A final state must be connected, because otherwise there would be two
vertices with no path between them, and then a transition adding the edge
between them would be possible, contradicting finality of the state.

A final state can't have a cycle, because deleting any edge on the
cycle would be a possible transition.}

\eparts

\end{examproblem}

\begin{examproblem}{20}
Let $L_n$ be the $n+1$-vertex simple ``line'' graph consisting of a
single simple path of length~$n$.  For example, $L_4$ is shown in the
figure below:

\begin{figure}[h]
\begin{center}
\begin{picture}(80,30)
\put(00,15){\circle*{3}} \put(00,15){\line(1,0){20}}
\put(20,15){\circle*{3}} \put(20,15){\line(1,0){20}}
\put(40,15){\circle*{3}} \put(40,15){\line(1,0){20}}
\put(60,15){\circle*{3}} \put(60,15){\line(1,0){20}}
\put(80,15){\circle*{3}}
\end{picture}
\end{center}

\centerline{The line graph $L_4$}
\end{figure}

Let's say a simple graph has ``two ends'' if it has exactly two
vertices of degree~one, and all its other vertices have degree~two.
In particular, for $n \ge 1$, the graph~$L_n$ has two ends. Consider
the following false theorem.

\paragraph{False theorem:}
Every simple graph with two ends is isomorphic to~$L_n$ for
some~$n~\ge~1$.

\begin{problemparts}
\problempart[5]
Draw a diagram of the smallest simple graph with two ends which is not
isomorphic to any line graph.

%%  What is the smallest $n \ge 1$ such that there is an
%%  $n+1$-vertex simple graph with two ends which is \emph{not} isomorphic
%%  to~$L_n$? \hint See part (d).\brule{2em}

\solution{
\begin{center}
\begin{picture}(80,30)
\put(00,15){\circle*{3}} \put(00,15){\line(1,0){20}}
\put(20,15){\circle*{3}}
\put(40,15){\circle*{3}} \put(40,15){\line(1,0){40}}
\put(60,35){\circle*{3}} \put(40,15){\line(1,1){20}}
\put(80,15){\circle*{3}} \put(80,15){\line(-1,1){20}}
\end{picture}\\
The smallest two-ended graph not isomorphic to any line graph.
\end{center}}

\problempart[15] Explain briefly, but clearly, where the following proof
goes wrong:


\paragraph{False proof:}
We prove by induction on the number, $n \ge 1$, of edges in a simple
graph, that every two-ended graph with $n$ edges is isomorphic
to~$L_n$.

(Base case $n = 1$): A simple graph with one edge can only consist of
the two vertices connected by that edge and some number of vertices
not attached to  any edge, i.e., vertices of degree~zero.  Since a
two-ended graph cannot have vertices of degree~zero, the only
two-ended graph with one edge must consist solely of the two vertices
connected by the edge, which makes it isomorphic to~$L_1$.

(Induction case): Assume that $n \ge 1$ and every two-ended graph with
$n$ edges is isomorphic to~$L_n$.  Now let $G_n$ be any two-ended
graph with $n \ge 1$ edges.  By hypothesis, $G_n$ is isomorphic
to~$L_n$.  Suppose an edge is added to~$G_n$ to form a two-ended
graph~$G_{n+1}$.

Since $G_n$ is isomorphic to~$L_n$, it consists of a simple path of
length~$n$.  The only way to add an edge to the path and preserve
two-endedness is to have that edge go from one end---that is, one of
the degree-one vertices---to a new vertex, lengthening the path by
one.  That is, the resulting $n+1$-edge graph must be a simple path of
length~$n + 1$, so it is isomorphic to~$L_{n+1}$.  Q.E.D.

\solution{
The inductive case is argued in an incorrect way.  The inductive case
must consist of a proof for any $n\ge{1}$ that if $G_{n+1}$ is
two-ended then $G_{n+1}\sim L_{n+1}$ ($A\sim{B}$ is a notation for ``$A$
is isomorphic to $B$''), using the assumption that for every two-ended
$G_n$, $G_n\sim{L_n}$ (alternatively, in strong induction, we can use
an assumption that for every $k$, $1\ge{k}\ge{n}$, if $G_k$ two-ended
then $G_k\sim{L_k}$).  

The false proof above does not argue that at all.  Instead, it states
that if one takes a two-ended $G_n$ which is isomorphic to $L_n$, and
extends it by an edge to form a two-ended $(n+1)$-edge graph $G'$,
then $G'\sim{L_{n+1}}$.  This is true, but to transform this argument
into an inductive proof, one would have to argue that every two-ended
$(n+1)$-edge graph $G_{n+1}$ can be formed in this way, i.e. by adding
another edge to some two-ended graph $G_n$.  However, this cannot be
argued because it is not true.  For example, in the solution to part
(a), we have a two-ended graph $G_4$ which cannot be formed by adding
an edge to some two-ended $G_3$.
}


\end{problemparts}
\end{examproblem}


\end{document}

