\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

% \problemdata       % Takes 5 *mandatory* arguments
% {natural-pred}     % latex-friendly label for the prob.
% {predicates}      % The topic(s) of the problem content.
% {}               % Source (if known)
% {F01 tut2-1}     % Usage (list ones you are aware of).
% Josh F02}        % Last revision info (author, date).

\begin{examproblem}{20}
Suppose $S(n)$ is a predicate on natural numbers, $n$, and suppose
\begin{equation}\label{Sk2}
\forall k \in \naturals \; S(k) \implies S(k+2).
\end{equation}
If~(\ref{Sk2}) holds, some of the assertions below must \emph{always}
(\textbf{A}) hold, some \emph{can} (\textbf{C}) hold but not always,
and some can \emph{never} (\textbf{N}) hold.  Indicate which case
applies for each of the assertions by \textbf{circling} the correct
letter.

\begin{problemparts}

\problempart[2]  \hspace{.2in} {\bf A C N \hspace{.2in}} 
$\forall n \ge 0\; S(n)$ 
\solution{\textbf{C}.
The assertion means that $S$ is always true.  So $S(k+2)$ is always true, and
therefore $S(k) \implies S(k+2)$ is always true.  So this case is possible.
But~\ref{Sk2} also holds when $S$ is always false, so the asertion does not
always hold when \ref{Sk2} does}

\problempart[2] \hspace{.2in} {\bf A C N \hspace{.2in}} $\neg{S(0)}
\land \forall n \ge 1\; S(n)$ 
\solution{\textbf{C}.
This time $S$ is false at 0, but true everywhere else.  So $S(k) \implies
S(k+2)$ still always holds because $S(k+2)$ is still always true.  So this
assertion can hold, but not always, since~(\ref{Sk2}) can hold when $S(0)$ is
true.}

\problempart[2]  \hspace{.2in} {\bf A C N \hspace{.2in}} 
$\forall n \ge 0\; \neg{S(n)}$
\solution{\textbf{C.}
Now $S$ is always false.  So $S(k) \implies S(k+2)$ is always true because
$S(k)$ is false.  So this case is possible, but again does not always hold.}

\problempart[2]  \hspace{.2in} {\bf A C N \hspace{.2in}} 
$(\forall n \le 100\; S(n)) \land (\forall n > 100\; \neg{S(n)})$ 
\solution{\textbf{N}.
In this case, $S$ is true for $n$ up to 100 and false from 101 on.  So $S(99)$
is true, but $S(101)$ is false.  That means that $S(k) \not \implies S(k+2)$
for $k = 99$.  This case is impossible.}

\problempart[2] \hspace{.2in} {\bf A C N \hspace{.2in}} $(\forall n
\le 100\; \neg{S(n)}) \land (\forall n > 100\; S(n))$ 
\solution{\textbf{C}.
In this case, $S$ is false for $n$ up to 100 and true from 101 on.  So $S(k)
\implies S(k+2)$ for $k \le 100$ because $S(k)$ is false, and $S(k) \implies
S(k+2)$ for $k \ge 99$ because $S(k+2)$ is true.  So this case is possible, but
again does not always hold}

\problempart[2]  \hspace{.2in} {\bf A C N \hspace{.2in}} 
$S(0) \implies \forall n\ S(n+2)$ 
\solution{\textbf{C}.
If $S(n)$ is always true this assertion holds.  So this case is possible.  If
$S(n)$ is true only for even $n$~(\ref{Sk2}) still holds, but $S(1+2)$ is
false.  So this case does not always hold.}

\problempart[2]  \hspace{.2in} {\bf A C N \hspace{.2in}} 
$S(1) \implies \forall n\ S(2n+1)$
\solution{\textbf{A}.
This assertion says that if $S(1)$ holds, then $S(n)$ holds for all odd $n$.
This case is always true.}

\problempart[2]  \hspace{.2in} {\bf A C N \hspace{.2in}} 
$[\exists n\, S(2n)] \implies \forall n \ S(2n+2)$
\solution{\textbf{C}.
If $S(n)$ is always true, this assertion holds.  So this case is possible.  If
$S(n)$ is true only for even $n$ greater than 4,~(\ref{Sk2}) holds, but this
assertion is false. So this case does not always hold.}

\problempart[2]  \hspace{.2in} {\bf A C N \hspace{.2in}} 
$\exists n\, \exists m > n\, [S(2n) \land \neg{S(2m)}]$
\solution{\textbf{N}.
This assertion says that $S(n)$ holds for some even number ($2n$) but not for
some other larger even number ($2m$).  However, if $S(2n)$ holds, we can
apply~(\ref{Sk2}) $n-m$ times to conclude $S(2m)$ also holds.  This case is
impossible.}

\problempart[2]  \hspace{.2in} {\bf A C N \hspace{.2in}} 
$[\exists n\, S(n)] \implies \forall n\, \exists m> n\, S(m)$
\solution{\textbf{A}.
This assertion says that if $S(n)$ holds for some $n$, then for every number,
there is a larger number $m$ for which $S(m)$ also holds.  Since~(\ref{Sk2})
implies that if there is one $n$ for which $S(n)$ holds, there are an infinite,
increasing chain of $k$s for which $S(k)$ holds, this case is always true.}

\iffalse
\problempart[2]  \hspace{.2in} {\bf A C N \hspace{.2in}} 
$\neg{S(0)} \implies \forall n \ \neg{S(2n)}$
\fi

\end{problemparts}
\end{examproblem}


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

% \problemdata     
% {F00-pquiz1}
% {precedence relations}
% {}              
% {F00-quiz1} 		
% {F00-nancy}

%% rewrote death as attila the hun and added dilworth part

\begin{examproblem}{15}
Attila the Hun is planning another excursion into a Roman
village. This requires a number of tasks, each of which takes him one
minute to complete.  The prerequisites associated with these tasks are
listed below.
\begin{center}
\begin{tabular}{cll}
\textsc{Abbrv.} & \textsc{Task} & \textsc{Prerequisites} \\
C & Assemble the barbarians & \\
N & Plunder the village & B \\
D & Get shots for his own cat, also named Emilios & B \\
B & Blow the trumpet & \\
T & Sell T-shirts: ``I got A LOT more than just this lousy t-shirt.'' &
N \\
Q & Grade the 6.042 quiz & S \\
G & Cook a feast & D,N \\
S & Burn the village & C,N 
\end{tabular}
\end{center}

\begin{problemparts}

\problempart[4] Draw the Hasse diagram for the tasks and their
prerequisites.
  
\solution[\vspace{2.5in}]{

Students received full credit for drawing a correct Hasse diagram showing the correct dependencies.  

Students missing edges or incorrectly drawing reflexive edges lost one point (Hasse diagrams never contain reflexive edges).

%FIX THE SOLUTION, find or recreate figure.

%% \centerline{\psfig{figure=figures/Hasse.jpg,height=2.5in}}

\begin{center}\includegraphics{figures/Hasse.jpg}\end{center}
}

\problempart[2] Attila has decided that since his barbarians are quite
smart and he has so many, he can get as many tasks done at a time as
he wishes.  What is the minimum amount of time required for him to
finish the excursion? \brule{4em}

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

This was an all or nothing problem.  Any answer other than 4 received no credit.
}

\eparts

It turns out that Attila's graph is actually far more complicated than the
one above.  In fact, he doesn't know what the actual diagram because his
Scribe forgot to tell him.  All Attila has been told is that he must
complete $n$ tasks, each of which takes 1 minute, and that the minimum
amount of time required to finish is $t$ minutes.  Without knowing
anything more about the actual graph, Attila is trying to figure out how
many barbarians to recruit.  A barbarian can only complete one task in 1
minute, but has the stamina to work for days on end.  Let $n$ and $t$ be
fixed, and $n>t>1$.

\bparts
\problempart[4] Write a simple formula in $n$ and $t$ for the smallest
number of barbarians Attila can recruit in order to be \emph{guaranteed}
to finish in $t$ minutes. \brule{4em}

\solution{There are $n$ tasks, $t$ is the longest chain.  We are
guaranteed that everything can be partitioned into $t$ antichains.

$n-t+1$.  In the worst case there could be an antichain of size
$n-t+1$ but no larger, which means that if Attila hired that many
barbarians he'd be set.

Some students wrote $n-t$ and ended up off by one, losing 2 points.

Almost any other answer received no credit.

}

\problempart[5] Write a simple formula in $n$ and $t$ for the smallest
number of barbarians he could recruit and still \emph{possibly} finish the
job in $t$ minutes.  (That is, if he recruits fewer barbarians, he will
never be able to finish in the minimum number, $t$, of minutes, no matter
how ``favorable'' graph turns out to be.) \brule{4em}

\solution{$\ceil{n/t}$.  Since there is no chain of size $t+1$, we know
that at least one antichain must have $\geq n/t$ elements.  If Attila
recruits fewer than $\ceil{n/t}$ barbarians, this antichain will take at
least two seconds, and there will still be $t-1$ stages to complete, so
there will be no chance he can get done in $t$ seconds.  

Many students simply wrote $n/t$ without ``ceiling'' and got 3 out of 5 points.

Some students realized that $n/t$ from Dilworth's theorem is not always an integer but said to ``round down'' or ``round to the nearest number'' or to take the ``floor plus one''.  All of these have cases that are incorrect, so these students received 4 out of 5 points.

A few students misunderstood the problem, which clearly says to write a simple formula in $n$ and $t$.  The previous paragraph also mentions specifically that $n$ and $t$ are known values and that the only unknown is the Hasse diagram. The students who thought that all of $n$, $t$, and the Hasse diagram were unknown wrote $2$, the rationale being that $n>t>1$ so $n=3$, $t=2$ is the most favorable scenario.  These students received 1 out of 5 points.

}

\end{problemparts}
\end{examproblem}


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

% \problemdata     
% {F01-quiz1}
% {relations}
% {}              
% {F01-quiz1} 		
% {F01 Meyer/Nagpal}

\begin{examproblem}{15} 
In this problem, let $R$ be a binary relation on a set $A$, and $S$ be
a binary relation from $A$ to a set $B$.  Indicate whether each of the
following statements is \textbf{True} or \textbf{False}.  For the
false ones, \textbf{\emph{describe a counterexample}}\footnote{No
explanation required for statements that are True.}.

\solution{Comments: Parts (a) and (c) were give 3 points for true
answers, 0 for false answers.  Parts (b), (d), and (e) were given 0
points for true answers, 1 point for the correct false answer and 2
more points for an appropriate counterexample.}

\begin{problemparts}

\problempart[3] If $R= R^*$, then $R$ is a transitive relation.\brule{.5in}

\solution[\vspace{1in}]{True}


\problempart[3] If $R= R^*$, then $R$ is an equivalence relation. \brule{.5in}

\solution[\vspace{1in}]{False. Counterexample: $A \eqdef \naturals,\
R \eqdef \le$}

\problempart[3] If $R$ is an equivalence relation, then $R= R^*$. \brule{.5in}

\solution[\vspace{1in}]{True.}

\problempart[3] If $A = B$, then $S \compose R = R \compose S$. \brule{.5in}

\solution[\vspace{1in}]{False.  Counterexample: $A = B \eqdef
\set{1,2,3}, R \eqdef \set{(1,2)}, S \eqdef \set{(2,3)},$ so $S
\compose R = \set{(1,3)}, R \compose S = \emptyset$.

Second counterexample: 
\begin{eqnarray*}
R & \eqdef & \set{(x, x+1) \suchthat x \in \reals},\\
S & \eqdef & \set{(x, 2x) \suchthat x \in \reals},
\end{eqnarray*}
because $2(x+1) \neq (2x) +1$.
}


\problempart[3] If $R = R^{-1}$ and $R$ is nonempty, then $R$ is
reflexive. \brule{.5in}

\solution[\vspace{1in}]{False.  Counterexample: $xRy \eqdef\ x\neq
y$ as long as $\card{A} \ge 2$.  Another counterexample:  $R = R^{-1} \eqdef
\set{(a,b),(b,a)}.$}

\iffalse
\problempart[3] If $R$ is the graph of a bijection $f:A \to A$, then
$R^{-1}$ is the graph of $f^{-1}$.  \brule{.5in}

\solution[\vspace{0.7in}]{True}
\fi



\end{problemparts}
\end{examproblem}

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

% Fall 97 Quiz 1
% Problem 4
% SIGNIFICANTLY REWRITTEN (Rad & ARM)

\begin{examproblem}{25}
Recall that a $k$-coloring of a simple graph is an assignment of a color
to each vertex such that no two adjacent vertices have the same color, and
no more than $k$ colors are used.  In class we proved
\begin{lemma*}
\emph{If a graph has maximum degree $k$, then it is $k+1$-colorable},
\end{lemma*}

\iffalse
A graph is defined to be {\em regular} if every vertex in the 
graph has the same degree

%% Testing whether or not they remember inclass coloring
%% Setting them up so that they understand the definitions

\problempart[3] Give an example of a regular graph with degree 2, that
requires $2+1=3$ colors.

\solution[\vspace{3in}]{A simple cycle of odd length.}


%% Generalize the idea to provide a counter-example to a theorem about
%% k-colorable...
\problempart[3] Consider the following false claim: A regular graph
with degree $k$ can not be colored in less than $k+1$ colors. Give a
counter-example to the claim.
\solution[\vspace{2in}]{An even cycle is an example of a regular
graphs with degree 2 that can be colored with 2 colors.}
% newpage
\ifshowsolutions {} \else \newpage \fi
\fi

Consider the following variation of this Lemma:
\iffalse graph must be connected for this to be true\fi

\begin{falseclm*}
A graph with maximum degree $k$ that also has a vertex of degree less than
$k$, is $k$-colorable.
\end{falseclm*}

\begin{problemparts} 
\problempart[5] Give a counterexample to the False Claim when $k=2$.

\solution[\vspace{2in}]{One node by itself, and a separate $K_3$. The
graph has max degree 2, but is not 2-colorable.}

Consider the following proof of the False Claim:

\begin{falseproof}

Proof by induction on the number $n$ of vertices:

{\bf Induction hypothesis:} 

$P(n) \eqdef\ $``Every graph with $n$ vertices and maximum degree $k$ that
also has a vertex of degree less then $k$, is $k$-colorable.''

{\bf Base case:} (n=1) 
The graph has only one vertex of degree zero, so $P(1)$ holds
vacuously.

{\bf Inductive step:} 

We may assume $P(n)$.  To prove $P(n+1)$, let $G_{n+1}$ be a graph with
maximum degree $k$ that has a vertex, $v$, of degree less than $k$.

Remove the vertex $v$ to produce a graph $G_n$.  Removing $v$ reduces the
degree of all vertices adjacent to $v$ by 1.  Therefore $G_n$ must contain
at least one vertex with degree less than $k$.  Also the maximum degree of
$G_n$ is at most $k$.  If the maximum degree of $G_n$ is less than $k$,
then by the Lemma above, $G_n$ is $k$-colorable.  Otherwise $G_n$ has
maximum degree $k$ and a vertex of degree less than $k$,
\iffalse
BETTER TO HAVE STARTED A NEW SENTENCE HERE
\fi
so by our
induction hypothesis, $G_n$ is $k$-colorable.  So in any case, $G_n$ is
$k$-colorable.

Now a $k$-coloring of $G_n$ gives a coloring of all the vertices of
$G_{n+1}$, except for $v$.  Since $v$ has degree less than $k$, there will
be fewer than $k$ colors assigned to the nodes adjacent to $v$.  So there
will be a color left over among the $k$ colors that can be assigned to
$v$.  Hence $G_{n+1}$ is $k$-colorable.
\end{falseproof}

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

\problempart[5] Identify the exact sentence where the proof goes wrong
(underlining or circling the sentence is sufficient).

\solution[\vspace{1in}]{``Therefore $G_n$ must contain at least one
vertex with degree less than $k$.''}

\problempart[5] Briefly explain why the sentence is incorrect.

\solution[\vspace{3in}]{This is only true if $v$ is adjacent to some other
vertex, but $v$ might not be connected to anything, \ie it might be of
degree zero.}

\problempart[5] The False Claim can be made true by adding an additional
assumption about the graph.  Which of the following is the most general
asumption that will make the False Claim true?\footnote{By ``most
general,'' we mean it is implied by all the other assumptions that verify
the False Claim.  For example, the assumption that $G$ is a line graph is
more general than the assumption that $G$ is a line graph with $3$
vertices.}

\begin{enumerate}
\item The graph is a line graph.
\item The graph has only even length cycles.
\item The graph is connected.
\item The graph does not contain a complete graph on $k$ vertices.
\item The graph has no node of degree zero.
\item The graph has a Hamiltonian cycle.
\item $k<2$.
\end{enumerate}

\solution[\vspace{.3in}]{``The graph is connected'' is the most general
sufficient assumption among those listed.  Being a linegraph or having a
Hamiltonian cycle are also sufficient, because both imply connectedness.
None of the other assumptions are sufficient.}

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

\problempart[5] Assuming that $G_{n+1}$ satisifes the additional
assumption from part (d), both the False Claim and the sentence that was
incorrect from part~(b) become correct.  But now another sentence in the
proof becomes incorrect and requires fixing.  Indicate the new incorrect
sentence and briefly explain what's wrong.  (You are \emph{not} expected
to suggest a fix.)

% \problempart[7] Why is it not sufficient to just add this condition to
% the hypothesis in order to make the false proof correct? What
% additional correction needs to be made to the proof?

\solution[\vspace{2in}]{The new false sentence is, ``Otherwise $G_n$ has
maximum degree $k$ and a vertex of degree less than $k$, \emph{so by our
induction hypothesis}, $G_n$ is $k$-colorable.''

The italicized phrase is wrong, because removing $v$ might leave a $G_n$
that is not connected, and such a $G_n$ would not satisfy the corrected
induction hypothesis, which requires that the graph is connected.  The fix
is to consider instead each connected component of $G_n$ separately.}

\end{problemparts} 
\end{examproblem}

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

%%  spring 01 practise quiz (karger)

\begin{examproblem}{25}
One of the three monks working on the famed Towers of Hanoi project
recently rubbed his pained back and burst out, ``Yo!  What are we
doing?  This is for chumps!  Let's punt!''  But before wandering off
to start up fast food joints, they must evenly divide the monastery's
collection of prayer beads.

Initially, monk $A$ has 5 beads, monk $B$ has 3 beads, and monk $C$
has 4 beads.  The monastic order has strict rules regarding the
exchange of prayer beads.  Only the following transactions are
allowed.

\begin{enumerate}

\item Monk $B$ may give a bead to monk $A$ at any time.

\item If $C$ has an odd number of beads, then monk $A$ may give a bead to
monk $B$.

\item If $C$ has an even number of beads, then monk $C$ may give or
take a bead from either monk $A$ or monk $B$.

\item If monk $A$ has at least two more beads than monk $B$, then monk
$C$ may give or take a bead from either monk $A$ or monk $B$.

\end{enumerate}

\begin{problemparts}
\problempart[10] Model the situation with a state machine.  Define the
set of states, the set of start states, and the set of transitions.

\solution[\vspace{5in}]{ The set of states $Q$ consists of all triples
$(a, b, c)$ such that $a, b, c \geq 0$ and $a + b + c = 12$.  The set of
starts states $Q_0$ consists of the single triple $(5, 3, 4)$.  There are
six types of transitions:
\[
\begin{array}{rcll}
(a, b, c) & \rightarrow & (a+1, b-1, c) &
        \quad \text{($b > 0$)} \\
(a, b, c) & \rightarrow & (a-1, b+1, c) &
       \quad \text{($a > 0$ and $c$ is odd)} \\
(a, b, c) & \rightarrow & (a-1, b, c+1) &
        \quad \text{($a > 0$ and either $c$ is even or $a \geq b + 2$)} \\
(a, b, c) & \rightarrow & (a, b-1, c+1) &
        \quad \text{($b > 0$ and either $c$ is even or $a \geq b + 2$)} \\
(a, b, c) & \rightarrow & (a+1, b, c-1) &
        \quad \text{($c > 0$ and either $c$ is even or $a \geq b + 2$)} \\
(a, b, c) & \rightarrow & (a, b+1, c-1) &
        \quad \text{($c > 0$ and either $c$ is even or $a \geq b + 2$)}
\end{array}
\]

(One point was taken off for omitting the ``$>0$'' conditions.)
}

\problempart[5] Describe a sequence of steps (transitions) leading to a
state where monk $A$ has 0 beads, monk $B$ has 9 beads, and monk $C$ has 3
beads.

\solution[\vspace{3in}]{ Initially, monk $C$ gives a bead to monk
$B$ using rule 3.  Then monk $A$ gives his 5 beads to monk $B$ using
rule 2.\ repeatedly. }

\problempart[4] A clever TA tells you that the following predicate is
an invariant.
\[
(C\text{ has an odd number of beads}) \lor (A \text{ has more beads than } B)
\]
\emph{Assuming} she is correct, prove that the monks can not reach the
state where every monk has 4 beads.

\solution[\newpage]{The invariant holds in the single start state
$Q_0$, since in this case monk $C$ has an even number of beads (4), and
monk $A$ has more beads than monk $B$ (5 vs.\ 3).  It does not hold when
all three Monks have 4 beads, since $C$ is even and $A$ and $B$ have the
same number of beads.  So by the Invariant Theorem, the 4-4-4 state cannot
be reachable.

It was necessary to show that the invariant holds for the start state,
which is key to proving that the state 4-4-4 is not reachable from it. 
}

\problempart[6] Now prove that the TA was correct in her assumption
that the predicate is an invariant.

\solution{
We have to show that if the TA's predicate holds before a transition, then
it holds after a transition.  There are six cases to check, corresponding
to the six types of transition.

\begin{enumerate}
\item $(a, b, c) \rightarrow (a+1, b-1, c)$ where $b > 0$.  If $c$ is odd,
then the invariant immediately holds after the transition.  If $c$ is
even, then the invariant holds after the transition because $a + 1 > a > b
> b - 1$.

\item $(a, b, c) \rightarrow (a-1, b+1, c)$ where $a > 0$ and $c$ is odd.
The invariant holds after the transition because $c$ is unchanged, so the
invariant immediately holds.

\item $(a, b, c) \rightarrow (a-1, b, c+1)$ where $a > 0$ and either $c$
is even or $a \geq b + 2$.  If $c$ is even, then the invariant holds after
the transition $c$ becomes odd.  If $c$ is odd, then the invariant holds
after the transition because monk A has (at least two) more beads than
monk B.
\end{enumerate}

The argument in the remaining three cases is identical to the argument
for case 3.

Remember the definition of an invariant from the course notes:

\textbf{Definition.} An {\em invariant} for a state machine is a predicate, 
$P$, on states, such that whenever $P(q)$ is true of a state, $q$, and $q 
\rightarrow r$ for some state, $r$, then $P(r)$ holds.

Notice that it is not necessary for an invariant to hold for the start
states.
}


\end{problemparts}
\end{examproblem}

\end{document}

