\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{psfig}
\usepackage{graphics}
\usepackage[pdflatex]{graphicx}
\input{macros-course}


\newif\ifspaceout
\spaceouttrue
\newcommand{\smallspace}{\ifspaceout\vspace{1in}\fi}
\newcommand{\mediumspace}{\ifspaceout\vspace{3in}\fi}
\newcommand{\largespace}{\ifspaceout\vspace{4in}\fi}
\newcommand{\nextproblem}{\ifspaceout\newpage\fi}

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

\newcommand{\bij}{\mathbin{\mbox{\rm bij}}}
\newcommand{\inj}{\mathbin{\mbox{\rm inj}}}
\newcommand{\sur}{\mathbin{\mbox{\rm sur}}}
\newcommand{\ran}[1]{\text{range}(#1)}
\newcommand{\Union}{\bigcup}

\newcommand{\eqdef}{\mathbin{\mbox{::=}}}

\newcommand{\ROT}{\mbox{ROT}}
\newcommand{\FBT}{\mbox{FBT}}
\newcommand{\brep}{\mbox{rot-to-fbt}}
\newcommand{\unrep}{\mbox{fbt-to-rot}}
\newcommand{\nil}{\mbox{\texttt{()}}}
\newcommand{\sz}{\mbox{size}}
\newcommand{\cons}{\mbox{cons}}
\newcommand{\sbtr}{\mbox{subtrees}}
\newcommand{\kcomp}[1]{\bar{#1}}

\newcommand{\fins}{\mathcal{F}}

\newcommand{\kpfend}{}

\newcommand{\kskip}[1]{}

\newcommand{\pts}[1]{\relax[#1 points]\enskip\ignorespaces}
\newcommand{\onept}{\relax[1 point]\enskip\ignorespaces}

\makeatletter
\renewcommand\theenumi{\@alph\c@enumi}
\renewcommand\theenumii{\@roman\c@enumii}

\renewcommand\labelenumi{\theenumi)}
\renewcommand\labelenumii{\theenumii)}

\def\ps@myheadings{%
    \let\@oddfoot\@empty\let\@evenfoot\@empty
    \def\@evenhead{\thepage\hfil\slshape\leftmark}%
    \def\@oddhead{\rlap{\slshape\rightmark}\hfil\thepage\hfil \llap{Name:\brule{2in}}}%
   \let\@mkboth\@gobbletwo
    \let\sectionmark\@gobble
    \let\subsectionmark\@gobble
    }

\makeatother

\askaboutsolutions

\begin{document}


\ifshowsolutions
{
\begin{center}
{\large \bf
Exam 1 Solutions}

October 24, 2000
\end{center}
\spaceoutfalse
\else
\begin{center}
{\large \bf
6.042 Exam 1}

October 18, 2000
\end{center}

\fi

\ifshowsolutions
\else
\smallspace


\begin{tabbing} 
\hspace{1.5in}\=Name:\hspace{1in}\=\underline{\hspace{2.5in}}\\
\\
\>Tutorial Leader:\>\underline{\hspace{2.5in}}\\
\\
\>DO NOT WRITE IN THIS SPACE
\end{tabbing}
\smallspace
\begin{eqnarray*}
\hbox{Problem 1:}& \underline{\hspace{1in}} & / \;\;30\\
\hbox{Problem 2:}& \underline{\hspace{1in}} & / \;\;25\\
\hbox{Problem 3:}& \underline{\hspace{1in}} & / \;\;15\\
\hbox{Problem 4:}& \underline{\hspace{1in}} & / \;\;\;8\\
\hbox{Problem 5:}& \underline{\hspace{1in}} & / \;\;32\\
\hbox{Problem 6:}& \underline{\hspace{1in}} & / \;\;30\\
\hbox{Problem 7:}& \underline{\hspace{1in}} & / \;\;40\\
\hbox{Problem 8:}& \underline{\hspace{1in}} & / \;\;20\\
\hbox{Total:}& \underline{\hspace{1in}} & / \;200
\end{eqnarray*}
\nextproblem
\fi


\begin{problems}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%   PROBLEM 1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{30} \textbf{Predicates and Quantifiers}

Use the following propositions where the universe of discourse is the
set of all natural numbers:

\begin{eqnarray*}
P(n):& n \hbox{ is a perfect square}\\
Q(n):& n \hbox{ is prime}\\
R(n,m):& n < m\\
S(n,m):& n \hbox{ divides } m\\
T(n,m):& n = m\\
\end{eqnarray*}

Express each of the following statements using quantifiers, logical
connectives, and the propositions listed above, along with variables and
integers.

\begin{problemparts}

\problempart {\bf (5 points)}  4 is a perfect square and 4 is greater than 1.

\solution{ 
\bigskip
{\bf Solution: }
$P(4) \wedge R(1,4)$ 
}
\bigskip

\smallspace

\problempart {\bf (5 points)}  There is a natural number that divides 
all natural numbers.

\solution{ 
\bigskip
{\bf Solution: }
$\exists n \forall m S(n, m)$
}

\bigskip

\smallspace

\problempart {\bf (5 points)} Two natural numbers are equal exactly
when neither is less than the other.

\solution{ 
\bigskip
{\bf Solution: }
$\forall n \forall m T(n, m) \leftrightarrow \neg R(n, m) \wedge
\neg R(m, n)$
}

\nextproblem

\problempart {\bf (5 points)} A natural number $n$ that is greater
than 1 is prime exactly when the only positive natural number less
than $n$ that divides $n$ is 1.

\solution{ 
\bigskip
{\bf Solution: }
$\forall n Q(n) \wedge R(1,n) 
\leftrightarrow [\forall m R(0, m) \wedge R(m, n)
\wedge S(m, n) \rightarrow T(m, 1)]$
}

\smallspace

\problempart {\bf (5 points)} A natural number $n$ is a perfect square
only if there is a positive natural number (strictly) between 1 and
$n$ that divides $n$.

\solution{ 
\bigskip
{\bf Solution: }
$\forall n P(n) \rightarrow [\exists m R(0, m) \wedge R(1, m) 
\wedge R(m, n) \wedge S(m, n)]$
}

\smallspace

\problempart {\bf (5 points)} Given only the statements (a)-(e) above
and the standard rules of propositional and quantifier reasoning, can
you conclude that 4 is not prime?  If not, state a fact you can use
together with the statements (a)-(e) to conclude that 4 is not prime
(your fact should not mention the number 4).  If so, just list which
of the statements (a)-(e) above are necessary.


\solution{
\bigskip
{\bf Solution: }
We can conclude that 4 is not prime, using parts (a), (c), (d), and (e).

Though a structured proof was not required, we provide one.  The
statement from part (c) was necessary so that we can use that if $m_0
> 1$ then $\neg m_0 = 1$.  Parts (d), and (e) are clearly required, and
part (a) is required so that we know 4 is a perfect square and that 4 > 1,
which are required to use the implications from (d) and (e).  Here is the
structured proof:


\begin{tabbing}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX\=XXXXXX\=\kill
1.  $P(4) \rightarrow [\exists m R(0, m) \wedge R(1, m) \wedge R(m, 4)
\wedge S(m, 4)]$\>UI, from part (e).\\
2.  $P(4)$\>Simplification, from part (a).\\
3.  $\exists x R(0, x) \wedge R(1, x) \wedge R(x, 4) \wedge S(x, 4)$
\>Modus Ponens, from 1 and 2.\\
4.  $R(0, m_0) \wedge R(1, m_0) \wedge R(m_0, 4) \wedge S(m_0, 4)$
\>EI, from 3.\\
5.  $R(1, m_0)$ \>Simplification, from 4.\\
6.  $T(1, m_0) \leftrightarrow \neg R(1, m_0) \wedge \neg R(m_0, 1)$
    \>UI, from part (c).\\
7.  $\neg R(1, m_0) \wedge \neg R(m_0, 1) \leftarrow T(1, m_0)$
    \>Simplification, from 6.\\
8.  $\neg [R(1, m_0) \vee R(m_0, 1)] \leftarrow T(1, m_0)$
    \>DeMorgan's law, from 7.\\
9.  $R(1, m_0) \vee R(m_0, 1)$  \>Addition, from 5.\\
10.  $\neg T(1, m_0)$  \>Modus Tollens, from 8 and 9.\\
11.  $R(0, m_0) \wedge R(m_0, 4) \wedge S(m_0, 4)$ \>Simplification,
     from 4.\\
12.  $(R(0, m_0) \wedge R(m_0, 4) \wedge S(m_0, 4)) \wedge \neg T(1,
     m_0)$ \>Conjunction, from 10 and 11.\\
13.  $\neg[\neg (R(0, m_0) \wedge R(m_0, 4) \wedge S(m_0, 4)) \vee
     T(1, m_0)]$ \>DeMorgan's Law, from 12.\\
14.  $\neg[(R(0, m_0) \wedge R(m_0, 4) \wedge S(m_0, 4)) \rightarrow
     T(1, m_0)]$ \>Logical equivalence, from 13.\\
15.  $\exists m \neg [(R(0, m) \wedge R(m, 4) \wedge S(m, 4))
     \rightarrow T(1, m)]$ \>EG, from 13.\\
16.  $\neg \forall m [(R(0, m) \wedge R(m, 4) \wedge S(m, 4)) \rightarrow
     T(1, m)]$ \>Negation rule for quantifiers\\
17.  $Q(4) \wedge R(1,4) \leftrightarrow [\forall m R(0, m) \wedge
     R(m, 4) \wedge S(m, 4) \rightarrow T(m, 1)]$ \>\>UI, from part (d).\\
18.  $\neg (Q(4) \wedge R(1,4))$  \>Modus Tollens, from 15 and 16.\\
19.  $\neg Q(4) \vee \neg R(1,4)$  \>DeMorgan's Law, from 18.\\
20.  $R(1,4)$ \>Simplification, from part (a).\\
21.  QED $\neg Q(4)$  \>Disjunctive Syllogism, from 19 and 20.  
\end{tabbing}}
\nextproblem

\end{problemparts}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%   PROBLEM 2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{25} \textbf{Relations}
\begin{problemparts}

For each relation listed in parts (a) through (e) circle {\em all} terms
listed that apply to it.

\problempart {\bf (5 points)}  $A = \{a, b\}, R = \{(a, a), (a, b)\}$.

\solution{ 
\bigskip {\bf Solution: }
This relation is antisymmetric and transitive.
}

\problempart {\bf (5 points)} $aRb$ whenever $a$ and $b$ are students
and either $a = b$ or $a$ has a GPA greater than or equal to that of
$b$.  (You may assume that all students have different GPAs).

\solution{
\bigskip {\bf Solution: }
This relation is reflexive, transitive and antisymmetric, so it is
a partial order.  Furthermore, since any two different students have
different GPAs, they can be compared with $R$.  Therefore, this 
relation is also a total order.
}

\problempart {\bf (5 points)} $aRb$ whenever $a$ and $b$ are real numbers
and $a = b^x$ for some rational number $x$.

\solution{
\bigskip {\bf Solution: }
This relation is not symmetric, since $1 = 4^0$ but $1^x$ is 1 for any 
rational number $x$.  However, it is not antisymmetric since $2 = 4^{.5}$
and $4 = 2^2$.  Thus is is none of these.
}

\problempart {\bf (5 points)}  $aRb$ whenever $a$ and $b$ are rational
numbers and $ab$ is an integer.

\solution{
\bigskip {\bf Solution: }
This relation is not reflexive (for instance, $\neg(.5R.5)$).
Therefore, it is none of these.
}


\problempart {\bf (5 points)} $aRb$ whenever $a$ and $b$ are integers such
that there is a nonnegative integer $k$ such that $3^k | a$ and $3^k | b$
and $3^{k+1}\not|a$ and $3^{k+1}\not|b$.  

\solution{\bigskip
{\bf Solution: }
This relation is essentially just saying that $3$ divides $a$ and $b$
the same number of times.  This is an equivalence relation, since
the same number of times is reflexive, symmetric and transitive.

} \nextproblem


\end{problemparts}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%   PROBLEM 3 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{15} \textbf{Directed Graphs}

Recall that a {\em tournament graph} is a directed graph in which
between any two different nodes $a$ and $b$ there is an edge either
from $a$ to $b$ or from $b$ to $a$ but not both, and there are no
other edges in the graph.

For each of the following, answer true or false and give a brief
justification of your answer.

\begin{problemparts}

\problempart{\bf (5 points)} There is no tournament graph on 4 nodes with
an Euler circuit.

\solution{
\bigskip {\bf Solution: }
The claim is true.

In a tournament graph on 4 nodes, every node will have an odd number
(3) of edges, so the degree of every node is odd.  A directed graph
has an Euler circuit only when every node has equal in-degree and
out-degree.  However, if the total degree (in-degree plus out-degree)
is odd, the in-degree and out-degree cannot be equal.  Thus, there is
no Euler circuit.
}

\smallspace

\problempart{\bf (5 points)} There is no tournament graph on 5 nodes
with an Euler circuit.


\solution{
\bigskip {\bf Solution: }
The claim is false.

An example is the graph on five nodes $a, b, c, d, e$ where the
edges are $(a,b),\, (b,c),\, (c,d),$ $(d,e),\, (e,a),\, (a,c),\,(c,e),\,
(e,b),\, (b,d),\,(d,a).$  The edges in this order make an Euler circuit.  
}

\smallspace

\problempart{\bf (5 points)} There is no tournament graph on 225 nodes with
an Euler circuit.

\solution{
\bigskip {\bf Solution: }
The claim is false.

The complete graph on 225 nodes has an Euler circuit, since every node
has degree 224, which is even.  Since an Euler circuit contains every
edge, all we have to do to construct a 225-node tournament graph with
an Euler circuit is take the Euler circuit on $K_{225}$ and choose a
direction, then include every edge in our 225-node tournament graph in
the direction it appears in the Euler circuit.  This will be a
tournament graph, since every two nodes are connected and every edge
is directed.

}

\nextproblem

\end{problemparts}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%   PROBLEM 4 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{8} \textbf{Structured Reasoning}

For this proof, fill in the predicate and quantifier rules used for
each step denoted with a *, and say which statements they are based on.


\begin{tabbing}
Given: $\forall x \exists y [Q(x, y) \vee R(x, y)]$\\
Prove: $\forall x [\exists y Q(x,y) \vee \exists y R(x,y)]$\\
Proof:\\
*\=XX\=*\=XX\=*\=XXXXXXXXXXXXXXXXXXXXXXXXX\=\kill
\>1.  Let $x_0$ be  arbitrary.\\         
\>2.  $\exists y [Q(x_0, y) \vee R(x_0, y)]$
\>\>\>\>\>Universal Instantiation, from Given\\
\>3.  $Q(x_0, y_0) \vee R(x_0, y_0)$
\>\>\>\>\>Existential Instantiation, from 2.\\
\>4.  $\exists y Q(x_0, y) \vee \exists y R(x_0, y):$\\
\>\>\>4.1.  case $i$:  Assume $Q(x_0, y_0)$.\\
\>\>\>\>*4.1.1.  $\exists y Q(x_0, y)$
\>\>\underline{\hspace{2in}}\\
\>\>\>\>*4.1.2.  $\exists y Q(x_0, y) \vee \exists y R(x_0,y)$
\>\>\underline{\hspace{2in}}\\
\>\>\>4.2.  case $ii$:  Assume $R(x_0, y_0)$.\\
\>\>\>\>\>4.2.1.  $\exists y R(x_0, y)$\\
\>\>\>\>\>4.2.2.  $\exists y Q(x_0, y) \vee \exists y R(x_0,y)$\\
\>\>*4.3. QED $\exists y Q(x_0, y) \vee \exists y R(x_0, y)$
\>\>\>\>\underline{\hspace{2in}}\\
*5. QED $\forall x [\exists y Q(x,y) \vee \exists y R(x,y)]$
\>\>\>\>\>\>\underline{\hspace{2in}}
\end{tabbing}

\solution{ {\bf Solution:}
4.1.1:  Existential Generalization, from 4.1

4.1.2:  Addition, from 4.1.1

4.3:  Proof by cases, from 3, 4.1.2, and 4.2.2

5:  Universal Generalization, from 1 and 4.3
}

\nextproblem

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%   PROBLEM 5 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{32} \textbf{Proof Comprehension}

For each of the following proofs, determine whether it is valid or
invalid.  If it is valid, say so.  If it is invalid, what about the
proof is incorrect?  (NOTE:  If you say a proof is valid, feel free
to give some explanation for why you think that proof is valid.  This
may give you some partial credit if you are incorrect.)

\begin{problemparts}

\problempart {\bf (8 points)}  

\begin{tabbing}
Theorem: 2 = 1.  \\
Proof:\\
1.  Assume $2 = 1$.\\
2.  $x^2 + 2 = x^2 + 1$.\\
3.  $2x dx = 2x dx$.  (differentiating both sides)\\
4.  $2 = 2$  (dividing both sides by $x dx$)\\
5.  Therefore, $2 = 1$ (QED)
\end{tabbing}

\solution{
\bigskip {\bf Solution: }
Step 5 is invalid.  After step 4 we have proven that $(2 = 1) \rightarrow
(2 = 2)$.  This is an implication, and is true even if $2 \neq 1$.  So
we can't conclude that $2 =1$.  This is known as the fallacy of affirming
the conclusion.
}

\smallspace

\problempart {\bf (8 points)}  

\begin{tabbing}
Theorem:  All rational numbers $x$ greater than
or equal to 1 are such that $x \leq 2^x$.\\
Proof:  Let $P(n)$ be the statement ``$n \leq 2^n.$''\\
1.  We know that $1 \leq 2^1 = 2$.  Therefore, $P(1)$.\\
2.  Assume $P(n)$ where $n \geq 1$.\\
3.  Then, $n \leq 2^n$\\
4.  Adding $1$ to both sides, we get $n + 1 \leq 2^n + 1$\\
5.  Substituting that $1 \leq n$, we get $n + 1 \leq 2^n + n$.\\
6.  Substituting from step 3 into the RHS of step 5, we get $n+1 \leq
    2^n + 2^n$\\
7.  Simplifying, we get $n+1 \leq 2^{n+1}$.\\
8.  Thus, $P(n+1)$.  Therefore, by induction, $\forall n P(n)$.
\end{tabbing}

\solution{ 
\bigskip {\bf Solution: }
This proof is invalid.  Step 7 is invalid, since $\forall n
P(n)$ would be a statement about the rational numbers (since that was
the statement of the theorem), but induction allows us to conclude only
that $\forall n \in {\Bbb N} \; P(n)$.  }

\nextproblem

\problempart {\bf (8 points)} 

Theorem: If $G$ is a finite graph with
positive integer-weighted edges that has a spanning tree, it has a 
minimal spanning tree (a spanning tree $T$ such that the
sum of the weights of the edges in $T$ is as small as it could be
for any spanning tree).

Proof:  Every spanning tree of $G$ has a total weight $w$ which is
non-negative integer.  Therefore, the set of possible total weights of
spanning trees is a subset of the non-negative integers.  By the
well-ordering property, since there is a spanning tree, there must be
a least weight of a spanning tree, and therefore there must be a
spanning tree that has that weight.  Thus, there is a minimal spanning
tree.

\solution{
\bigskip {\bf Solution: }
This proof is valid.  
}

\problempart {\bf (8 points)} 

Theorem: There are infinitely many prime numbers.

Proof: Let $S$ be the set of all prime numbers.  Now let $k = 1 +
\prod_{p \in S} p$.  Note that $k$ is not divisible by any $p$ in $S$
since the remainder when dividing by $p$ would be 1.  Furthermore,
notice that if $p$ is any element of $S$ then $k = 1 + \prod_{q \in S}
q \geq 1 + p > p$.  But this is a contradiction.  Therefore, there
must be infinitely many prime numbers.

\solution{
\bigskip {\bf Solution: }
The proof is sloppy enough to be considered invalid.

This is basically just like the classical proof that there are
infinitely many primes, but it's sloppily done.  Here are the two
significant problems with the proof, from minor objections to major
ones.

1.  The author never explains why what has been derived about $k$
causes something new to be prime.  It should be mentioned that either
$k$ must be prime, or it must contain a prime factor not in $S$, which
is what creates the contradiction.  This is a serious omission, but
since this omission could just be filled in, it is not something bad
enough to make the proof invalid.

2.  Most importantly, the author never includes the assumption that
$S$ is finite.  If $S$ is infinite, the whole argument falls apart
since $k$ would not be a number and so everything that's reasoned
about $k$ would be invalid.  This is serious enough that the proof
is not valid without it.

}

\nextproblem

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%   PROBLEM 6 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{30} \textbf{Hamiltonian Circuits}
\begin{problemparts}


In this problem you will prove that for any positive integer $n$, any 
$2n$ by $2n$ grid graph has a Hamiltonian circuit.  

An $n$ by $m$ grid graph is made up of vertices described as pairs of 
integers $(x, y)$ where $0 \leq x < n$ and $0 \leq y < m$.  There is
an edge between two vertices if their $x$-coordinates differ by 1 or
if their $y$-coordinates differ by 1 but NOT if both differ by 1.

So, for example, there would be edges between the vertices $(2,3)$ and
$(3,3)$ but not between $(2,3)$ and $(3,2)$.

\problempart {\bf (4 points)}  Draw a 4 by 4 grid graph.  Label vertices
$(1, 3)$, $(2, 2)$, and $(2, 3)$.  

\solution{
\bigskip
{\bf Solution: }
\begin{center}
{\includegraphics[height=3.0in]{figures/quiz1p6a}}
\end{center}
}

\smallspace

\problempart {\bf (10 points)} Prove that the chromatic number of any
$m$ by $n$ grid graph is 2 (for $m, n > 1$).

\solution{
\bigskip {\bf Solution: } To prove that the chromatic number of an $m$
by $n$ grid graph is 2, we must show that it cannot be colored with 1
color, and that it can be colored with 2 colors.

Since $m,n > 1$, there is an edge from $(0,0)$ to $(0, 1)$, so the
graph cannot be 1-colored, since these two vertices must have different
colors.

To color the graph with 2 colors, simply let all vertices $(x,y)$
where $x + y$ is even be colored white, and let all vertices where
$x+y$ is odd be colored black.  Since nodes are only adjacent to other
nodes where $x$ or $y$ differs by 1, but not both, we see that every
node adjacent to $(x,y)$ is such that the sum of that nodes
coordinates is either $x+y-1$ or $x+y+1$.  Thus, any white node is
adjacent only to black nodes, and vice versa.  

}

\nextproblem

\problempart {\bf (16 points)} Prove by induction that any $2n$ by
$2n$ grid graph has a Hamiltonian circuit for $n \geq 1$.  (Other
proof methods will not get credit) Note: this question does not have
anything to do with the question in part (b).

\solution{
\bigskip {\bf Solution: }
Let $P(n)$ be the statement ``Any $2n$ by $2n$ grid graph has
a Hamiltonian circuit.''

$P(1)$:  Any 2 by 2 grid graph is just a square.  The square itself
is a circuit, and it touches all the nodes.  Thus, it is a Hamiltonian
circuit.

Assume $P(n)$.  Let $G$ be a $2(n+1)$ by $2(n+1)$ grid graph.  We
construct a Hamiltonian circuit for $G$ as follows.  First, let the
subgraph on all the vertices with $x < 2n$ and $y < 2n$ be called
$H$.  $H$ is a $2n$ by $2n$ grid graph, so it has a Hamiltonian circuit.

Start at vertex $(0, 2n+1)$ and continue straight to $(2n+1, 2n+1)$
and then down to $(2n+1, 0)$, then to $(2n, 0)$.  Now, since we know
there's a Hamiltonian circuit in $H$, pick one.  $H$ must include
the edge from $(2n-1, 0)$ to $(2n-1, 1)$ since in $H$, vertex $(2n-1, 0)$
has degree 2.  

Now we continue our path to vertex $(2n-1, 0)$ and through the circuit 
for $H$ in the direction of $(2n-2, 0)$.  After visiting all the nodes
in $H$, this will return us to $(2n-1, 1)$.  From there we continue to 
$(2n, 1)$ and up to $(2n, 2n)$ and back to $(0, 2n)$ and we close the
circuit by going back to $(0, 2n+1)$.  

Thus, $P(n+1)$.  By induction, if $n$ is an integer $\geq 1$ then
Any $2n$ by $2n$ grid graph has a Hamiltonian circuit.
}

\nextproblem

\end{problemparts}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%   PROBLEM 7 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{40} \textbf{State Machines and Invariants}
\begin{problemparts}

Consider the following algorithm, that, given a number, produces
the prime factorization of that number.  The prime factorization of
a number is a list of all primes that divide that number, where
primes may be listed multiple times if they divide the number multiple
times.  The product of all the numbers in the list should be equal
to the original number.

Assume that  Append ($List, i$) takes a list and adds the element
$i$ to the beginning of it.  Assume that $()$ refers to the list
with no elements.

\begin{tabbing}
FactorPrime $(n \in {\mathbb N})$:\\
1.  $i := 2.$\\
2.  $List := ().$\\
3.  $m := n.$\\
4.  \=IF \=$m = 1$ THEN\\
       \>\>FactorPrime$(n)$: = $List$.\\
5.    IF   $i | m$ THEN\\      
       \>\>Append ($List, i$).\\
       \>\>$m := m/i$.\\
    \>ELSE\\
       \>\>$i := i+1$.\\
6.  Go to step 4.\\
\end{tabbing}

\problempart {\bf (10 points)}  Represent this algorithm as a state
machine.

\solution{
\bigskip{\bf Solution:}

The states of the machine can be described by 

$$Q = \{(i, m, List)| i, m \in {\Bbb Z}, List \hbox{ is a list of integers}\}$$

The starting state on input $n$ is $(2, n, ())$.  The transitions
are described by:

\begin{tabbing}
$\delta(i, m, List)$\= = nothing if $m=1$,\\
                    \> = $(i, m/i, $Append$(List,i))$ if $i|m$, or\\
                    \> = $(i+1, m, List)$ otherwise.
\end{tabbing}
}

\nextproblem

\problempart {\bf (10 points)} Using an invariant, prove that if the
algorithm ever gets to the point where $m = 1$, then the list is a
factorization (not necessarily a prime factorization) of its input
$n$.

\solution{
\bigskip{\bf Solution:}
The following is the invariant we will use.

$P(i,m,List)$: ``The product of all the numbers in $List$ and the
number $m$ equals $n$.''

To prove that this is an invariant, we note that since the start state
of the state machine is $(2, n, ())$, the product of all the numbers
in $List$ and $m$ is just $m$, which is $n$.

Now suppose that $P(i,m,List)$ is true.  We wish to prove that
$P(\delta(i,m,List))$ is true.  We proceed by cases.

{\bf Case 1:}  $i|m$.  Then, $\delta(i,m,List) = (i, m/i, Append(List,i))$.

Note that if the product of all numbers in list was $k$, the
product of all numbers in Append($List, i$) would be $ki$.  Therefore,
since $km = n$ then $(ki)(m/i) = km = n$ also, so $P(\delta(i,m,List))$ is
true.

{\bf Case 2:}  $i\not|m$.  Then, $\delta(i,m,List) = (i+1,m,List)$.

Since $m$ and $List$ are unchanged, the invariant continues to hold.

Therefore, $P(i,m,List)$ is an invariant of our state machine.  So, if $m=1$,
then the product of all the numbers in $List$ must equal $n$.  Thus,
$List$ is a factorization of $n$.
}



\mediumspace

\problempart {\bf (10 points)}  Prove that the list
never contains any numbers that are not prime.  

\solution{
\bigskip{\bf Solution:}
The following is the invariant we will use.

$R(i,m,List)$ = ``$List$ contains no non-prime numbers, and no
        numbers (other than 1) less than i divide $m$."

In the start state, the list contains no numbers at all so it cannot contain
any non-prime numbers.  Finally, there are no numbers less than 2
other than 1, so $R(2,n,())$ is true.

Now suppose we know that $R(i,m,List)$ is true.  We will prove that
$R(\delta(i,m,List))$ is true.  There are two cases:

{\bf Case 1:}  $i|m$.  Then, $\delta(i,m,List) = (i, m/i, Append(List,i))$.

If no numbers less than $i$ divide $m$, then no
numbers less than $i$ divide $m/i$ since $m/i$ divides $m$.

We must also prove that Append($List, i$) contains no non-prime
numbers. The only element in Append($List, i$) that is not in $List$
(which we know contains no non-prime numbers) is $i$.  Thus, we are
asked to prove that $i$ is prime, which we do by contradiction.
Suppose $i$ is not prime.  Then $i$ has a prime factor smaller than
$i$ other than 1: call it $h$.  Since $h|i$ and $i|m$ we know that
$h|m$.  But, since $R(i,m,List)$ is assumed, there can be no numbers
smaller than $i$ other than 1 which divide $m$.  Thus, by
contradiction, we see that $i$ is prime.  Therefore,
$R(\delta(i,m,List))$.

{\bf Case 2:}  $i\not|m$.  Then, $\delta(i,m,List) = (i+1,m,List)$.

Since $List$ did not change, it cannot contain any non-prime
numbers, since $R(i,m,List)$ is true.  

Also, we must verify that no numbers less than $i+1$ other than 1
divide $m$.  The only number less than $i+1$ which is not less than
$i$ is $i$ itself.  However, we know that $i$ does not divide $m$.

Therefore, $R(\delta(i,m,List)$.

Since $R$ is an invariant, it is clear that in particular, $List$
never contains any numbers that are not prime.

}

\nextproblem
\problempart {\bf (10 points)} Prove that this algorithm always
terminates.  

\solution{
\bigskip{\bf Solution:}
The following is a termination function:  

$f(q) = n+m-i$. 

This function is always decreasing because either type of transition
decreases it: one increases $i$, while the other decreases $m$.

This function is always an integer, since $n$ and $i$ are clearly
always integers, and $m$ is divided by $i$ only when $i|m$, so $m$ is
also always an integer.

By our invariant from part (b), we know that $m | n$, so therefore $m
\leq n$.  We now prove that $i \leq n$.  Suppose not.  Then, since $i
> m$, by our invariant from part (c), we know that there is no prime
less than $i$ that divides $m$ other than 1, so $m$ must be 1.
(Otherwise, $m$ would have a prime factor which would be less than or
equal to itself, and therefore less than $i$) But then since $m=1$ the
previous state must have been $(i, i, List)$ for some $List$ (it could
not have been $(i-1, 1, List)$ since there are no transitions when
$m=1$).  Thus, $i | n$ which implies that $i \leq n$.

Thus, $f(q)$ is always positive.  It achieves its lowest value when
$m$ is as small as possible and $i$ is as large as possible.  Since
$m \geq 1$ and $i \leq n$, this shows that $f(q) \geq 1$.  

By the termination theorem, the algorithm terminates.
}



\nextproblem


\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%   PROBLEM 8 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{20}  Bags and Stacks

This problem involves two labeled state machines,
called $\ms{Bag}$ and $\ms{Stack}$, each of which keeps track of a
collection of integers. 
A ``client'' can interact with each using requests and responses.
Both support the same kinds of operations: $\ms{insert}$ and
$\ms{get}$, though the operations behave a little differently in the
two machines.

$\ms{Bag}$ maintains a ``bag'' of integers, which is like a set of
integers except it allows repeats. 
Written out in detail: 
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\= \kill
$\ms{Bag}$ Labeled State Machine: \\
\\
$Q$: 
\> $B$, a bag of integers \\
\> $\ms{req}$, either $\ms{insert}(x)$, $\ms{get}$, or $\ms{null}$ \\
\> $\ms{resp}$, either $\ms{OK}$, an integer, $\ms{error}$, or
$\ms{null}$ \\
\\
$Q_0$: 
\> $B$ is the empty bag, $\ms{req} = \ms{resp} = \ms{null}$ \\
\\
$L$:
\> Input: $\ms{insert}(x)$, $\ms{get}$ \\
\> Internal: $\ms{perform}(\ms{insert}(x))$,$\ms{perform}(\ms{get})$ \\
\> Output: $\ms{respond}(r)$\\
\\
$\delta$:
\> $\ms{insert}(x)$:\\ 
\> \> Can occur:  Anytime \\ 
\> \> Effect: if $\ms{req} = \ms{null}$ then $\ms{req} := \ms{insert}(x)$ \\
\> $\ms{get}$: \\
\> \> Can occur:  Anytime \\
\> \> Effect: if $\ms{req} = \ms{null}$ then $\ms{req} := \ms{get}$ \\
\> $\ms{perform}(\ms{insert})$: \\
\> \> Can occur if: $\ms{req} = \ms{insert}(x)$ \\
\> \> Effect: add $x$ to $B$; $\ms{resp} := $\ms{OK} \\
\> $\ms{perform}(\ms{get})$: \\
\> \> Can occur if: $\ms{req} = \ms{get}$ \\
\> \> Effect: \\
\> \> \> if $B$ is nonempty then \\
\> \> \> \> choose any element $x$ in $B$ and remove one copy from $B$; \\
\> \> \> \> $\ms{resp} := x$ \\
\> \> \> else $\ms{resp} := \ms{error}$ \\ 
\> $\ms{respond}(r)$: \\
\> \> Can occur if: $\ms{resp} = r$, $r \not= \ms{null}$ \\
\> \> Effect: $\ms{req} := \ms{null}$; $\ms{resp} := \ms{null}$
\end{tabbing}

\nextproblem
The other machine, $\ms{Stack}$, differs from $\ms{Bag}$ only in its
state and the $\ms{perform}$ transitions:
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\= \kill
$\ms{Stack}$ Labeled State Machine: \\
\\
$Q$: 
\> $S$, a sequence of integers \\
\> $\ms{req}$, $\ms{resp}$, as for $\ms{Bag}$ \\
\\
$Q_0$:
\> $S$ is the empty sequence, $\ms{req} = \ms{resp} = \ms{null}$ \\
\\
$\delta$:\> $\ms{perform}(\ms{insert})$: \\
\> \> Can occur if: $\ms{req} = \ms{insert}(x)$ \\
\> \> Effect: $S = x S$, where $x S$ is the concatenation of $x$ and $S$; \\
\> \> \>  $\ms{resp} := $\ms{OK} \\
\> $\ms{perform}(\ms{get})$: \\
\> \> Can occur if: $\ms{req} = \ms{get}$ \\
\> \> Effect: \\
\> \> \> if $S$ is nonempty then \\
\> \> \> \> $\ms{resp} := \ms{head}(S)$ (the first element of $S$); \\
\> \> \> \> $S := \ms{tail}(S)$ (all but the first element)\\
\> \> \> else $\ms{resp} := \ms{error}$ 

\end{tabbing}

For this problem, you need give only a trace or an abstraction relation
that works to justify your answer.  If you give an abstraction relation,
you do not have to prove it is correct.

\problempart{\bf (10 points)}
Does $\ms{Stack}$ implement $\ms{Bag}$?
If your answer is yes, then give an abstraction
relation.  If it is no, then give an example of a
trace of $\ms{Stack}$ that is not a trace of $\ms{Bag}$.  


\solution{\bigskip 

{\bf Solution:} Yes.  An abstraction relation from {\em Stack} to {\em Bag}
is as follows:

$$(S, req, resp) \to (B_S, req, resp)$$

where the multiset $B_S$ is defined as follows: $B_S = \{x | x$
appears in $S\}$.  That is $x$ appears in $B_S$ exactly as many times
as it appears in the sequence $S$.  All transition labels are given
the same names.  }
\smallspace


\problempart{\bf (10 points)} Does $\ms{Bag}$ implement $\ms{Stack}$?
If so, give an abstraction relation.  If not, give a 
trace of $\ms{Bag}$ that is not a trace of $\ms{Stack}$.

\solution{\bigskip

{\bf Solution:} No.  Let $x$ and $y$ be different.

The trace {\em insert(x), respond(OK), insert(y), respond(OK), get, respond(x)}
is a trace of {\em Bag} but it is not a trace of {\em Stack}.  In stack, the
only available transition after the {\em get} would be a {\em respond(y)}.  
Since $x \neq y$, the two are different.  }








\end{problems}

\end{document}
