\documentclass[11pt,twoside]{article}   
\usepackage{latex-macros/course}

\def\bparts{\begin{problemparts}}
\def\eparts{\end{problemparts}}
\def\ppart{\problempart}

\renewcommand{\reading}{ \href{http://theory.lcs.mit.edu/classes/6.042/spring02/handouts/lectures/ln5.pdf}
{Week 5 Notes}, Rosen \S 3.3-5 }
\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

%\hidesolutions         
%\showsolutions

\begin{document}
\problemset{5}          

%%%%%%%%%%%%%%%%%%%%%%% PROBLEM %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5

\begin{problem} 
The \textbf{Fifteen Puzzle} consists of sliding square tiles numbered
$1,\dots,15$ held in a $4\times4$ frame with one empty square.  Any tile
adjacent to the empty square can slide into it.  The
\href{http://theory.lcs.mit.edu/classes/6.042/spring02/}{6.042 Icon} is
based on this puzzle.

The standard initial position is
\[\begin{array}{|c|c|c|c|}
\hline 1 & 2 & 3 & 4\\
\hline 5 & 6 & 7 & 8\\
\hline 9 & 10 & 11 & 12\\
\hline 13 & 14  & 15 &  \\
\hline
\end{array}\]
We would like to reach the target position (known in my youth as ``the
impossible'' --- ARM):
\[\begin{array}{|c|c|c|c|}
\hline 15 & 14 & 13 & 12\\
\hline 11 & 10 & 9 & 8\\
\hline7 & 6 & 5 & 4\\
\hline3 & 2 & 1 & \\
\hline
\end{array}\]

A state machine model of the puzzle has states consisting of a $4\times 4$
matrix with 16 entries consisting of the integers $1,\dots,15$ as well as
one ``empty'' entry---like each of the two arrays above.

The state transitions correspond to exchanging the empty square and an
adjacent numbered tile.  For example, a empty at position $(2,2)$ can
exchange position with tile above it, namely, at position $(1,2)$:
\[\begin{array}{|c|c|c|c|}
\hline n_1 & n_2 & n_3 & n_4\\
\hline n_5 &  & n_6 & n_7\\
\hline n_8  & n_9 & n_{10} & n_{11}\\
\hline n_{12} & n_{13} & n_{14}  & n_{15}\\
\hline
\end{array} \longrightarrow
\begin{array}{|c|c|c|c|}
\hline n_1 &   & n_3 & n_4\\
\hline n_5 & n_2 & n_6 & n_7\\
\hline n_8  & n_9 & n_{10} & n_{11}\\
\hline n_{12} & n_{13} & n_{14}  & n_{15}\\
\hline
\end{array} 
\]

In this problem you will use the invariant method prove that starting
from the initial state, there is no way to reach the target state.

We begin by noting that a state can also be represented as a pair
consisting of two things:
\begin{enumerate}

\item a list of the numbers $1,\dots,15$ in the order in which they
appear---reading rows left-to-right from the top row down, ignoring the
empty square, and

\item the coordinates of the empty square---where the upper left
square has coordinates $(1,1)$, the lower right $(4,4)$.

\end{enumerate}

Let $L$ be such an ordered list of the numbers $1,\dots,15$.  A pair of
integers is an \emph{out-of-order pair} in $L$ when the first element of
the pair both comes \emph{earlier} in the list \emph{and is larger}, than
the second element of the pair.  For example, the list $1,2,4,5,3$ has two
out-of-order pairs: 4,3 and 5,3.  The increasing list $1,2\dots n$ has no
out-of-order pairs.

Representing a state, $S$, as the pair $(L, (i,j))$ described above,
define the \emph{parity} of $S$ to be the mod 2 sum of the number of
out-of-order pairs in $L$ and the row-number, $i$, of the empty
square.

\begin{problemparts}

\problempart Verify that the parity of the initial state and the parity of the
target state are different.

\solution{The parity of the initial state is $(0+4) \bmod 2 = 0$.
Parity of target is $((15 \cdot 14/ 2) + 4) \bmod 2 = 1$.}

\problempart Show that the parity of a state is invariant under transitions.
Conclude that ``the impossible'' is impossible to reach.

\solution{To show that the parity is constant, let us consider what
types of moves may affect the parity.  The only 4 moves we need to worry
about are the following:  a move to the left, a move to the right, a move
to the row above, or a move to the row below.  

Note that horizontal moves change nothing, and vertical moves both change
$i$ by 1, and move a tile three places forward or back in the list, $L$.
To consider how the parity is changed in this case, we need to consider
only the 3 pairs in $L$ that are between the tile's old and new position.
(The other pairs are not effected by the tile's move).  This reverses the
order of three pairs in $L$, changing the number of inversions by 3 or 1,
but always by an odd amount.

To confirm this last remark, note that if the 3 pairs were all out of
order or all in order before, the amount is changed by 3.  If two pairs
were out of order and 1 pair was in order or if one pair was out of order
and two were in order, this will change the amount by 1.  So the sum of
$i$ and the number of out-of-order pairs changes by an even amount (either
1+3 or 1+1), which implies that its parity remains the same.  Since the
initial state has parity 0 (even), all states reachable from the initial
state must have parity 0, so the target state with parity 1 can't be
reachable.}

\ppart (optional, extra credit) Show that if two states have the same
aprity, then there is a way to get from one to the other.

\end{problemparts}
\end{problem}

\begin{problem}
\textbf{Extended GCD} We have already proved in two different ways that
the gcd of two natural numbers can be expressed as an integer linear
combination of them.  The following procedure extends the Euclidean GCD to
explicitly calculate the desired integer coefficients.

In particular, given natural numbers $m,n$, with $n>0$, we claim the
following procedure halts with integers $K,L$ in registers \texttt{K} and
\texttt{L} such that
\[
Km+Ln=\mbox{gcd}(m,n).
\]
(This procedure and its invariants are taken from Aho, Hopcroft, and
Ullman's text on algorithms.)

Inputs: $m,n \in \naturals, n>0$.

Registers: \texttt{X,Y,K,L,U,V,Q}.

\begin{verbatim}
X := m; Y := n; K := 0; L := 1; U := 1; V := 0; 
loop:
if Y|X, then halt
else
 Q := floor(X/Y);      ;; same as Q:= quotient of X divided by Y
 {X := Y,              ;; assignments within the braces are SIMULTANEOUS
  Y := X - Q * Y,      ;; same as Y:= remainder of X divided by Y
  U := K,
  V := L,
  K := U - Q * K,
  L := V - Q * L}     ;; assignments within the braces are SIMULTANEOUS
goto loop
\end{verbatim}

Note that \texttt{X,Y} behave exactly as in the Euclidean GCD algorithm
from lecture, except that this procedure stops one step sooner, ensuring
that $\mbox{gcd}(m,n)$ is in \texttt{Y} at the end.

\bparts

\ppart Prove that this procedure terminates for all inputs $m,n$.

\solution{It terminates for the same reason as the Euclidean algorithm:
the contents, $Y$, of register \texttt{Y} is a natural number-valued
variable that strictly decreases each time around the loop.}

\ppart We claim that invariant properties that can be used to prove partial
correctness are:
\begin{itemize}
\item %\label{gcd}
(a)  $\mbox{gcd}(X,Y) = \mbox{gcd}(m,n)$,
\item % \label{kl}
(b) $Km+ Ln = Y$, and
\item % \label{uv}
(c) $Um+Vn = X$.
\end{itemize}

Prove that (a), (b) and (c) are ``loop'' invariants, that is, if they are
true at the start of the loop, they are true at the start of the next
loop.

\solution{Invariant (a) is the same one as for the Euclidean algorithm, which
we proved in lecture.  To check the other two invariants, note that at the
start $X=m, Y=n, K=0, L=1$ so $Km+Ln=0m+1n=n=Y$ as required; also $U=1, V=0$
and $Um+Vn= 1m+0n=m =X$ as required.

So let $x,y,k,l,u,v$ be the contents of registers \texttt{X,Y,K,L,U,V} at
the start of the loop and assume that all the invariants hold for these
values.  We must prove that (b) and (c) hold (we already know (a) does)
for the new contents $x',y',k',l',u',v'$ of these registers at the next
time the loop is started.

Now according to the procedure, $u'=k,v'=l,x'=y$, so invariant (c) holds
for $u',v',x'$ because of invariant (b) for $k,l,y$.  Also, $k'= u - qk,
l'= v - ql, y' = x - qy$ where $q = \floor{x/y}$, so
\[k'm+l'n = (u-qk)m + (v-ql)n =um+vn - q(km+ln) = x - qy = y',\]
and therefore invariant (b) holds for $k',l',y'$.
}

\ppart Prove that at termination, \texttt{Y} contains $\mbox{gcd}(m,n)$
and \texttt{K} and \texttt{L} contains integers $K$ and $L$ such that
\[
\mbox{gcd}(m,n) = Km+Ln.
\]

\solution{It's easy to check that all three invariant are true at the
start of the first time around the loop.  So they are true at termination.
At termination the contents, $Y$, of register \texttt{Y} divides the
contents, $X$, of register \texttt{X}, so invariants (a) and (b) imply
\[
\mbox{gcd}(m,n) = \mbox{gcd}(X,Y) = Y = Km + Ln.
\]
So we have the gcd in register \texttt{Y} and the desired coefficients in
\texttt{K}, \texttt{L}.}

\eparts
\end{problem}


\begin{problem} \textbf{Structural Induction}

Suppose we start with a sequence of fully parenthesized arithmetic or
Scheme expressions, and then erase all the alphanumeric characters other
than parentheses.  The result is a string of parentheses which ``match
up''.

For example, erasing non-parenthesis characters from the expression
\texttt{(if (or x y) u v)} leaves the string \texttt{(())}.  Similarly,
erasing non-parentheses from the sequence of three arithmetic expressions
\[
\texttt{(x * x), (y + (3 * (z - 9))), ((x + y) * (u + w))}
\]
leaves the string
\[
\texttt{()((()))(()())}.
\]
On the other hand, even though the string \texttt{())(()} has an equal
number of left and right parentheses, it cannot be obtained by erasing in
this way---because the two middle parentheses don't match up.  Also, no
string of parentheses which begins with a right parenthesis or ends with a
left parenthesis can match up.

We can give an inductive definition of the set, SMU, of ``Strings which
Match Up'', as follows:

\begin{itemize}
\item The empty string (consisting of no parentheses) is an SMU.

\item If $s$ and $t$ are SMU's, then the string $\texttt{(}s\texttt{)}t$
is an SMU.  That is, the new string starts with a left parenthesis which
is followed by the parenthesis characters in the string $s$, followed by a
right parenthesis, followed by the parenthesis characters in the string
$t$.

\end{itemize}


There is a simple test to determine whether a string of parentheses is an
SMU: starting with zero, read the string from left to right adding one for
each left parenthesis and -1 for each right parenthesis.  A string
\emph{counts well} when the count never goes negative and is back to zero
by the end of the string.  Let CW be the set of strings of parentheses
which Count Well.

\begin{problemparts}
\problempart Prove that CW contains SMU by structural induction on the
definition of SMU.

\solution{We prove by induction on the definition of SMU (that is,
structural induction) that every element of SMU counts well, so SMU is
contained in CW.  The induction hypothesis is
\[
P(s) ::\equiv s \in \mbox{CW}.
\]
\begin{proof}

{\bf Base Case}: $P(\mbox{empty string})$ holds since the count of the
empty string ends when it starts at zero.

{\bf Inductive Step:} Assume $P(s)$ and $P(t)$ are true.  We need to show
that $P(\texttt{(}s\texttt{)}t)$ is true.

The count values for $\texttt{(}s\texttt{)}t$ start with 0.  Reading the
initial left parenthesis yields 1 as the next count value.  This 1 serves
as the start of a series of count values exactly equal to the count values
of $s$, with each value incremented by one.  Since $s \in \mbox{CW}$ by
hypothesis, these incremented count values begin with 1, always stay
positive, and end with 1.  The right parenthesis immediately after $s$
reduces the ending count to 0.  This 0 serves as the start of the
remaining count values which are exactly the count values of $t$.  Since
$t \in \mbox{CW}$, these remaining values never go negative and end at 0.
Hence the entire sequence of count values for $\texttt{(}s\texttt{)}t$
starts with 0, never goes negative, and ends with 0, which proves that
$\texttt{(}s\texttt{)}t \in \mbox{CW}$.
\end{proof}}

\problempart Conversely, prove that SMU contains CW.

\solution{We show that every string $r\in \mbox{CW}$ is an SMU by
strong induction on the length of $r$.  The induction hypothesis is
\[Q(n) ::\equiv \forall r \in \mbox{CW}(\mbox{if $r$ is length $n$, then
$r \in \mbox{SMU}$}).\]
\begin{proof}

{\bf Base Case} $n = 0$: In this case there is only one string of length
$n$, namely the empty string, which is in SMU by definition, proving
$Q(0)$.

{\bf Inductive Step:} Assume that $Q(k)$ is true for all $k\leq n$, we
need to prove that $Q(n+1)$ is also true.

So suppose $r$ is a length $n+1$ string that counts well.  We must prove
that $r \in \mbox{SMU}$.

Now since $r$ counts well, it must start with a left parenthesis (or else
the count would immediately go negative).  Likewise, since the count for
$r$ returns to the value 0 by the end, $r$ must end with right
parenthesis.  So there must be a \emph{first} right parenthesis in $r$
after which the count returns to 0.  Let $s$ be the substring of $r$
between the initial left parenthesis and this right parenthesis.  So
\[
r = \texttt{(}s\texttt{)}t
\]
for some string $t$.

Since counts only change by one as each parenthesis character is read, and
the count for $r$ \emph{first} returns to 0 after the right parenthesis
following $s$, the count during $s$ must start and end with 1 and must
stay \emph{positive} in between.  But this implies that a count for $s$
alone, which would start with 0, would also end with 0 and stay
\emph{nonnegative} in between.  That is, $s$ by itself counts well.  Since
the length of $s \in \mbox{CW}$ is less than the length of $r$, we have by
strong induction that $s \in \mbox{SMU}$.

Further, we know the count for $r$ returns to 0 after the right
parenthesis following $s$, and since $r \in \mbox{CW}$, the count ends
with 0 again and stays nonnegative in between.  But this implies that $t$
counts well, and since the length of $t$ is less than the length of $r$,
we have by strong induction that $t \in \mbox{SMU}$.  Now by the second
case in the definition of SMU, we conclude $\texttt{(}s\texttt{)}t$,
namely $r$, is in SMU.
\end{proof}}

\end{problemparts}
\end{problem}

\begin{problem}
Four VI-A students would like a position at a company.  There are four
companies, each with one position for a VI-A student.  Below are the
students' rankings of the companies and the companies' rankings of the
students.

\begin{center}
\begin{tabular}{l|c} 
Student & Ranking of Companies \\ \hline
Nikos   & Lotus, IBM, Compaq, Akamai \\
Yu-Han  & Compaq, Lotus, Akamai, IBM \\
Radhika & Compaq, Lotus, IBM, Akamai\\
Tina    & Akamai, Compaq, Lotus, IBM 
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{l|c}
Company & Ranking of Students \\ \hline
Compaq  & Yu-Han, Tina, Nikos, Radhika \\
Lotus   & Yu-Han, Radhika, Nikos, Tina \\
IBM     & Radhika, Yu-Han, Nikos, Tina \\
Akamai  & Tina, Yu-Han, Radhika, Nikos
\end{tabular}
\end{center}

Based on the rankings, the VI-A office will assign one student to each
company so the assignment forms a stable marriage set.

\bparts

\ppart There are VI-A student, $S$, and a company, $C$, that would form a
rogue pair in \emph{any} assignment in which $S$ was not assigned to $C$.
Give an example of such a pair $(S,C)$, and briefly explain why your
example has this property.

\solution{Tina likes Akamai best and Akamai likes Tina best.  So these
two would be sure to prefer each other over their spouses if they were not
married, \ie they would be a rogue pair if they were not married.  Yu-Han
and Compaq are another such pair.}

\ppart Verify that in this case, the Mating Algorithm yields the same
assignment whether Students are treated as Boys or as Girls.

\solution{Either way, the result is the following assignment:
\begin{center}
\begin{tabular}{l|l|} 
Student & Companies \\ \hline
Nikos  & IBM \\
Yu-Han     & Compaq \\
Radhika   & Lotus\\
Tina    & Akamai
\end{tabular}
\end{center}
}

\ppart Explain why this implies that there is only one possible stable
assignment (even including possible stable assignments that may not be
produced by the Gale/Shapley Mating Algorithm).

\solution{In the student-optimal (pessimal) assignment, a student $S$,
is assigned to their most (least) preferred company, $C$, among all
possible companies they could be assigned to in a stable assignment.  So
in any stable assignment, $S$ would be to be assigned to a company they
like no worse than $C$ nor more than $C$, so they have to be assigned to
$C$ no matter what.}

\eparts
\end{problem}




\iffalse

\begin{problem}
% source: Fall 2000 Problem Set 5
% topics: Matching, intuition

Give an example of a stable match between 3 boys and 3 girls
where no person gets their first choice.

\solution{Call the boys $1, 2, 3$ and the girls $a, b, c$.  Consider
the following preference list:

\begin{center}
\begin{tabular}{llll||llll} \hline
choice& 1st& 2nd& 3rd& choice& 1st& 2nd& 3rd \\ \hline
1& a& b& c& a& 2& 3& 1 \\
2& b& c& a& b& 3& 1& 2 \\
3& c& a& b& c& 1& 2& 3 \\ \hline
\end{tabular}
\end{center}
   
The matching $(1, b), (2, c), (3, a)$ is stable even though no person
gets their first choice.  

To see the intuition behind this solution, notice first that the first
choice of any boy has that boy as her last choice and vice versa.  
Second, notice that everyone ends up with their second choice.  

Since we show a pairing where everyone has their second choice, this 
is stable because the only way to have a rogue pair is for a boy
or girl to want their first choice, but their first choice always 
likes them least so will never want to leave their current partner.  
Therefore, we end up with a stable pairing where no one gets their
first choice.}
\end{problem}



%twang
%FALL01 - last used on tutorial 8
%Learning objectives:  7 (calculate numbers of possible outcomes)
%		       4 (graph theory)
%revised with newer graphic and edited solutions
%%Fall 99, Tutorial 9

\begin{problem}
\textbf{Counting Numbered Trees.}  A \emph{numbered tree} is a
tree whose vertex set is $\set{1,2,\dots,n}$ for some $n \geq 2$.  We
define the \emph{code} of the numbered tree to be a sequence of $n-2$
integers from 1 to $n$ obtained by the following recursive process:
\begin{quotation}\noindent
If $n=2$, stop---the code is the empty sequence.  Otherwise, write down
the \emph{father} of the largest leaf, delete this \emph{leaf}, and
continue the process on the resulting smaller tree.
\end{quotation}
For example, the codes of a couple of numbered trees are shown in

Figure~(\ref{fig:n-2}).
\begin{figure}[htb]
\begin{center}
\includegraphics[width=4in]{figures/n-2}
\end{center}
\caption{Coding Numbered Trees}
\label{fig:n-2}
\end{figure}

\bparts

\ppart Describe a procedure for reconstructing a numbered tree from its
code.

\solution{
The key observation is that, given a code of length $n-2$, the numbers
between 1 and $n$ which \emph{do not appear} in the code must be leaves of
the tree.  Hence, the largest missing number is a leaf attached to the
first number of the code.  The rest of the tree can now be reconstructed
by deleting the first number in the code, henceforth ignoring the largest
leaf, and proceeding recursively on the rest of the code.  (We're using
the obvious fact that what's left after deleting a leaf from a tree is
another tree.)

More precisely, the reconstruction procedure applies to any finite tree
whose vertex set is totally ordered.  The procedure takes \emph{two}
parameters: the vertex set, $V$, and a length $\card{V}-2$ ``code''
sequence, $S$, of elements in $V$.  If $l$ is the largest element in $V$
which does not appear in $S$, and $f$ is the first element of $S$, then
the reconstructed tree is obtained by adding edge $(l,f)$ to the tree
reconstructed by calling the procedure recursively with first argument
$V-\set{l}$ and second argument equal to the code obtained by erasing the
initial $f$ from $S$.  The procedure terminates when $\card{V}=2$,
returning the edge between the two numbers in $V$.

To justify the key observation, note that any vertex that gets deleted by
the process and was not a leaf to begin with, must have been the father of
a previously deleted leaf, which means it would appear in the code.  So
the missing integers must have been leaves to begin with or must be one of
the two undeleted vertices left when the coding process terminates.  But
by the end of the process the two remaining vertices are leaves, and if
they weren't leaves to begin with, they must have become leaves by having
their sons deleted, which means they would not have been missing from the
code.  So the two vertices remaining at the end must also have been leaves
of the original tree.
}

\ppart How many numbered trees with $n$ vertices are there?

\solution{There are exactly as many $n$-vertex numbered trees a there
are length $n-2$ sequences of numbers between 1 and $n$.  So there are
$n^{n-2}$ numbered trees.

The reason there are the same number is that the tree reconstruction
procedure takes any such length $n-2$ sequence and returns an $n$-vertex
numbered tree whose code it is.  But the explanation above of why the
recursive reconstruction procedure is correct actually shows more: the
reconstructed tree is the \emph{unique} one with that code.

Now since every such length $n-2$ sequence is the code of some $n$-vertex
numbered tree, the coding procedure defines a surjection.  Since the tree
with that code is unique, the coding coding procedure also defines an
injection.  So the tree-coding function is a bijection.  Therefore the
number of numbered trees with $n$ vertices is the same as the number of
length $n-2$ sequences of integers between 1 and $n$.}

\eparts
\end{problem}

%Final F01
\begin{problem} In tutorial we considered algorithms for coding a numbered
tree as a sequence of numbers and vice-versa.  In this problem we consider
methods to prove properties of a procedure for extracting the tree coded by
a number sequence.  The trees are undirected and unrooted.

The procedure will construct a tree with $n$ vertices numbered
$1,\dots,n$ from an input that is a sequence, $s$, of $n-2$ numbers
each between $1$ and $n$.  The procedure works by adding edges to a
graph, $G$, with vertices $1,\dots,n$, deleting elements from a set,
$I$, of vertices called the \emph{incomplete vertices}, and deleting
successive elements of a sequence, $t$, of numbers.

Given input $s$, the procedure goes as follows:
\begin{enumerate}

\renewcommand{\labelenumi}{P\arabic{enumi}.}
\renewcommand{\labelenumii}{P\arabic{enumi}.\arabic{enumii}}

\item Initialize $G$ to be the graph with vertices $\set{1,\dots, n}$
and no edges, where $n \eqdef \abs{s}+2$.  Initialize $t \eqdef s$ and
$I \eqdef \set{1,\dots,n}$.

\item Repeat the following loop of instructions until there remain exactly
two incomplete vertices, that is, until $\card{I} = 2$:

\begin{enumerate}
\item Let $l$ be the largest vertex in $I$ that does not occur in $t$.

\item $I \eqdef I - \set{l}$.

\item Add the edge $(l, \text{first}(t))$ to $G$,
where \text{first}(t) is the first number in $t$.

\item $t \eqdef \text{rest}(t)$, where $\text{rest}(t)$ is the sequence of
numbers in $t$ after the first.
\end{enumerate}

\item Add to $G$ the edge between the remaining two vertices in $I$ and
terminate.

\end{enumerate}

\bparts

\ppart Is this algorithm deterministic or nondeterministic?  No
explanation necessary.

\solution{Deterministic}

\ppart Draw the graph generated by the following code: 72357

\ifshowsolutions \else \vspace*{2in}\fi

\solution{Will draw these in.}

\ifshowsolutions \else \newpage \fi

\ppart\label{alg-invs} For each of the following derived variables,
indicate whether, from one time around the loop to the next, it is
\begin{itemize}
\item[\textbf{I}] Increasing
\item[\textbf{D}] Decreasing,
\item[\textbf{C}] Constant,
\item[\textbf{NI}] Nonincreasing but not constant or decreasing,
\item[\textbf{ND}] Nondecreasing but not constant or increasing,
\item[\textbf{N}] or None of these.
\end{itemize}
For example,
\begin{quotation}\noindent
\vspace{-.4in}
\begin{itemize}

\item $\abs{t}$  \hfill\brule{1in}D.

\item $\card{E_G} \bmod 2$, where $E_G$ is the set of edges of
$G$. \hfill\brule{1in}N.

\end{itemize}
The length of $t$ is decreasing because its first element is removed each
time around the loop.  The parity of the number of edges of $G$ has none
of the other growth properties because edges are added one at a time
around the loop, so it alternates between 0 and~1.
\end{quotation}
This is a short-answer question, so do \textbf{not} include explanations
like the ones above.

\begin{enumerate}

\addtolength{\leftskip}{0.25in}%
% Change this next line to modify numbering style.
% Current style: roman numeral followed by )
\renewcommand{\labelenumi}{\roman{enumi})}

\item the number of vertices of $G$.  \hfill\brule{1in}

\solution{
C; the vertices are always $\set{1,\dots,n}$.
}

\item $\card{E_G}$, the number of edges in $G$.  \hfill\brule{1in}

\solution{I; an edge is added each time around}

\item
$\card{I}$, the number of incomplete vertices. \hfill\brule{1in}

\solution{D; a vertex is removed each time around.}

\item
$\card{I} - \abs{t}$, the number of incomplete vertices, minus the length
of $t$. \hfill\brule{1in}

\solution{C; always equals 2.}

\item $\card{\text{nums}(t)}$, where $\text{nums}(t)$ is the set of numbers
that occur in $t$. \hfill\brule{1in}

\solution{NI; stays the same when the first element of $t$ occurs in $t$
more than once.}

\item the number of vertices of $G$ not touching an edge.
\hfill\brule{1in}

\solution{NI; won't decrease when two nonisolated components are
connected.}

\iffalse

\item the predicate: $\text{nums}(t) \subset I$. \hfill\brule{1in}

\solution{C: always true.}

\fi

\iffalse
\item $\card{I-\text{nums}(t)}$, the number of incomplete elements that do
not appear in $t$. \hfill\brule{1in}

\solution{NI; stays the same when the first element of $t$ is not
repeated.}
\fi

\iffalse

\item
$\card{E_G} + \card{I}$ \hfill\brule{1in}

\solution{C; always equals $n$; but not obvious.}
\fi


\iffalse

\item the number of connected components of $G$ minus $\card{I}$.
\hfill\brule{1in}

\solution{C; equals 0}
\fi

\item
the number of connected components of $G$. \hfill\brule{1in}

\solution{D; but not obvious.

The problem statement says the result is a numbered tree, so $G$ has one
connected component on termination.  But $G$ initially has $n$ components,
and adding an edge can only reduce the number of components by one and
there are only $n-1$ edges in the final tree, so
the edge added each time around the loop must reduce the number of
compoennts.

Proving this without assuming that the final result is a tree needs a more
general invariant that each connected component contains \emph{exactly}
one incomplete element.  Since only edges between incomplete elements are
added, this implies that when an edge is added, it connects different
components.}

\iffalse

\item the maximum number of vertices in $I$ in any connected component of
$G$. \hfill\brule{1in}

\solution{C; always 1}
\fi

\item the number of cycles in $G$. \hfill\brule{1in}

\solution{C; always 0}

\addtolength{\leftskip}{-0.25in}%
\end{enumerate}

\ppart How many edges are in $G$ when the procedure terminates?
\hfill\brule{1in} 

\solution{$n-1$ or $\card{s}+1$} 

\ppart How many connected components does $G$ have on termination?
\hfill\brule{1in}

\solution{1}

\ppart How many possible trees are there with vertices numbered
$\set{1,\dots, n}$? \hfill\brule{1in}

\solution{$n^{n-2}$}

\eparts
\end{problem}

% source: pset6 fall 01 problem 3
% topic: buckets
% last used:

\begin{problem} We are given two buckets, $A$ and $B$, a water hose, a
receptacle, and a drain.  The buckets and receptacle are initially
empty.  The buckets are labeled with their respectively capacities,
positive integers $a$ and $b$.  The receptacle can be used to store an
unlimited amount of water, but has no measurement markings.  Excess
water can be dumped into the drain.  Among the possible moves are:
\begin{enumerate}
\item\label{hose-bucket} fill a bucket from the hose,
\item pour from the receptacle to a bucket until the bucket is full
or the receptacle is empty, whichever happens first,
\item empty a bucket to the drain,
\item\label{bucket-receptacle} empty a bucket to the receptacle,
\item pour from $A$ to $B$ until either $A$ is empty or $B$ is full,
whichever happens first,
\item pour from $B$ to $A$ until either $B$ is empty or $A$ is full,
whichever happens first.
\end{enumerate}

\begin{problemparts} 
\problempart
Model this scenario with a state machine.  (What are the states?  How does
a state change in response to a move?)

\solution{
The states are triples $(x,y,z)$ which give the current amount of
water in the bucket $A$, bucket $B$, and the receptacle, respectively.
The initial state is $(0,0,0)$.

The moves make the following transitions:
\begin{enumerate}
\item fill a bucket from the hose
$$
(x,y,z) \rightarrow \left \{ \begin{array}{l}
(a,y,z) \mbox{ if filling A from the hose } \\
(x,b,z) \mbox{ if filling B from the hose }
\end{array} \right.
$$

\item pour from the receptacle to a bucket until the bucket is full
or the receptacle is empty, whichever happens first
$$ 
(x,y,z) \rightarrow \left \{ \begin{array}{l} 
(a,y,z-(a-x)) \mbox{ if pouring to A and } z \geq (a-x) \\
(x+z,y,0) \mbox{ if pouring to A and } z < (a-x) \\
(x,b,z-(b-y)) \mbox{ if pouring to B and } z \geq (b-y) \\
(x,y+z,0) \mbox{ if pouring to B and } z < (b-y) 
\end{array} \right.
$$

\item empty a bucket to the drain
$$
(x,y,z) \rightarrow \left \{ \begin{array}{l}
(0,y,z) \mbox{ if emptying A to the drain } \\
(x,0,z) \mbox{ if emptying B to the drain }
\end{array} \right.
$$

\item empty a bucket to the receptacle
$$
(x,y,z) \rightarrow \left \{ \begin{array}{l}
(0,y,z+x) \mbox{ if emptying A to the receptacle } \\
(x,0,z+y) \mbox{ if emptying B to the receptacle }
\end{array} \right.
$$

\item pour from $A$ to $B$ until either $A$ is empty or $B$ is full,
whichever happens first
$$ 
(x,y,z) \rightarrow \left \{ \begin{array}{l} 
(0,y+x,z) \mbox{ if } x < (b-y) \\
(x-(b-y),b,z) \mbox{ if } x \geq (b-y)
\end{array} \right.
$$

\item pour from $B$ to $A$ until either $B$ is empty or $A$ is full,
whichever happens first
$$ 
(x,y,z) \rightarrow \left \{ \begin{array}{l} 
(x+y,0,z) \mbox{ if } y < (a-x) \\
(a,y-(a-x),z) \mbox{ if } y \geq (a-x)
\end{array} \right.
$$
\end{enumerate}
}

\problempart
\label{gcd-iff}

Prove that we can put $k\in\naturals$ gallons of water into the
receptacle using the above operations if and only if $\mbox{gcd}(a,b) \mid k $.
\hint Use the fact that if $a,b$ are positive integers then there
exist integers $s,t$ such that $\mbox{gcd}(a,b)=sa+tb$ (proven in
Pset 2).

\solution{
We need to prove two facts (the ``iff'' statement has two directions):
\begin{enumerate}
\item
If $\mbox{gcd}(a,b) \mid k $ then we can put $k$ gallons of water into
the receptacle.

\begin{proof}

Since there exist integers $s,t$ s.t.  $\mbox{gcd}(a,b)=sa+tb$, then
if $\mbox{gcd}(a,b) \mid k $ then there exists an integer $n$ s.t. $n
* \mbox{gcd}(a,b) = k$, and hence $n(sa+tb)=k$.  Assume without loss
of generality that $sa\geq{tb}$ (otherwise exchange the buckets in the
following argument).  Then we can fill the receptacle with $k$ gallons: \\
First, we repeat $ns$ times moves $1$ and $4$, filling the $A$ bucket
and pouring its content into the receptacle (note that if $sa\geq{tb}$
then $s\geq{0}$).  With this series of moves we will get from state
$(0,0,0)$ to $(0,0,nsa)$.  Then, if $t=0$, we are already done since
$k=nsa$.  If $t>0$, we repeat $nt$ times moves $1$ and $4$ but now
using the bucket $B$.  This gets us from $(0,0,nsa)$ to
$(0,0,nsa+ntb)=(0,0,k)$.  If $t<0$ we repeat $n*(-t)$ times moves $2$
and $3$ using the bucket $B$.  At the end of this series we will be in
state $(0,0,nsa-n*(-t)b)=(0,0,nsa+ntb)=(0,0,k)$
\end{proof}

\item
If we can put $k$ gallons of water into the receptacle then
$\mbox{gcd}(a,b) \mid k $.

\begin{proof}
We show that it is an invariant of our state machine that
$\mbox{gcd}(a,b)$ divides $x$, $y$ and $z$.  It will prove in
particular, that $z$ is always a multiple of $\mbox{gcd}(a,b)$

Let's denote $\mbox{gcd}(a,b)$ by $c$.  The invariant is true in the
initial state $(0,0,0)$.\footnote{Remember that $(x\mid
y)\iff(\exists_{b\in\integers}\,\,\,y=xb)$}.  Each move preserves this
invariant, because in each move the new values of $x,y$ or $z$ are
always integer linear combinations of the previous values $x,y,z$ or
$a,b$, i.e., they are expressed by a formula
$n_1x+n_2y+n_3z+n_4a+n_5b$ for some
$(n_1,n_2,n_3,n_4,n_5)\in\integers^5$.  For example in move 2, case 1,
the new value of $z$ is expressed by the above formula with
$(n_1,n_2,n_3,n_4,n_5)=(1,0,1,-1,0)$.  Since $c$ divides $a$ and $b$,
if $c$ divides $x,y,z$ before the move, then it divides every such
linear formula, and hence it divides the values of $x,y$ and $z$ after
each move.
\end{proof}
\end{enumerate}
}

% \problempart Let's restrict the valid moves to numbers~\ref{hose-bucket}
% and~\ref{bucket-receptacle} only.  Prove that there exists a number
% $n$, such that for all integer $k\geq n$, we can fill the receptacle
% with $k$ gallons of water iff $\mbox{gcd}(a,b) \mid k$.

% \solution{
% Again, pick $s,t$ s.t. $c=\mbox{gcd}(a,b)=sa+bt$.  If both
% $s,t\geq{0}$ then $(s,t)=(0,1)$ or $(1,0)$, i.e., $a=b$ (check that in
% all other cases $c$ would be greater than either $a$ or $b$, which is
% impossible).  If $a=b$ then $c=a=b$, and for each $k\geq{c}$, $c\mid
% k$, we can fill the receptacle by repeating moves $1$ and $4$
% ${k}/{c}\in\naturals$ times (with any bucket, since $a=b$).

% Clearly it cannot be that both $s,t\leq0$ (or $c$ would be a
% non-positive integer).  So we are left with two cases: $t<0<s$ or
% $s<0<t$.  Assume without loss of generality that $t<0<s$.

% We show that if $k\geq{n}$ for $n=-t{b^2}/{c}$, and $k$ is a
% multiple of $c$, then we can fill the receptacle with $k$ gallons.
% Let's denote $k$ as a multiple of $b$ plus a ``remainder'' in the
% following way:
% %
% $$ k=k_1b+k_2c\mbox{, where
% }k_1,k_2\in\naturals\,\,\wedge\,\,0\leq{k_2}<\frac{b}{c} $$
% %
% We can represent $k$ in this way since it is divisible by $c$.  Notice
% also, that since $k\geq{-t{b^2}/{c}}$, then
% $k_1\geq{-t{b}/{c}}$.  Since $c=sa+bt$, we can rewrite $k$ as
% follows:
% \begin{eqnarray*}
% k&=&k_1b+k_2c
% \\
% &=&k_1b+k_2(sa+bt)
% \\
% &=&(k_2s)a+(k_1+k_2t)b
% \end{eqnarray*}
% Hence, as long as $k_1\geq{-t{b}/{c}}$, both $(k_2s)$ and $(k_1+k_2t)$
% are non-negative integers.  And hence, we can fill the receptacle by
% $(k_2s)$ times pouring bucket $A$ into it, and then $(k_1+k_2t)$ times
% bucket $B$, both just with moves $1$ and $4$.
% }

\end{problemparts}
\end{problem}



\fi


\end{document}                            
