\documentclass[11pt,twoside]{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
\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

\def\lexle{\mathrel{\preceq_{\text{lex}}}}
\def\lex<{\mathrel{\prec_{\text{lex}}}}
\def\coordle{\mathrel{\preceq_{\text{c}}}}
\def\coord<{\mathrel{\prec_{\text{c}}}}

\begin{document} 
\inclassproblems{4}                    % !! start the paper

\begin{problem} 
By now you are very familiar with the
\href{http://theory.lcs.mit.edu/classes/6.042/fall03/}{6.042 icon} that
appears on the course webpage and every lecture slide.  This icon is a
picture of a game called the \textbf{Fifteen Puzzle}.  In this problem you
will establish a basic property of the Fifteen Puzzle using the method of
invariants, and, if this exercise works as planned, you will come to
appreciate why this icon was chosen as the 6.042 logo.

The 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 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, an 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} 
\]

We will use the invariant method to prove that there is no way to reach
the target state starting from the initial 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}

\bparts
\ppart Write out the ``list'' representation of the start state and the
``impossible'' state.

\solution{
start: ((1\ 2\ \dots\ 15), (4,4)),

impossible: ((15\ 14\ \dots\ 1), (4,4)), 
}
\eparts

Let $L$ be a list of the numbers $1,\dots,15$ in some order.  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 and \emph{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.

Let a state, $S$, be a pair $(L, (i,j))$ described above.  We 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 of the empty square (\emph{i.e.}, $(L + i) \bmod 2$).

\begin{problemparts}

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

\solution{The parity of the start state is
\[
(0+4) \bmod 2 = 0.
\]
The 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, consider how moves may
affect the parity.  There are only 4 moves types of moves: 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.}

\end{problemparts}

By the way, if two states have the same parity, then in fact there
\emph{is} a way to get from one to the other.  If you like puzzles, this
is a good one to think about on your own about after class.

\end{problem}

\instatements{\newpage}

\begin{problem}

Consider the following game for two players.  The players alternate moves.
A move consists of a pair $(x,y)$ of natural numbers, subject to the
constraint that none of the previous moves may be $\coordle$ than the
current move, where $\coordle$ is the coordinatewise partial order.  An
equivalent way to say this is that the current move must be $\coord<$ or
incomparable to all the previous moves.  A player who moves to the origin
$(0,0)$ is the loser.

For example, the Player 1 might choose (5,6), after which Player 2 can
move to any point $(n,m)$ such that $n<5$ or $m<6$, for example, (4,12).
Now the players might move successsively to (4,11), (29,5), (1,1), (0,54),
(0,1).  At this point it's Player 2's turn, and he can move to to (1,0).
At this point it is Player 1's move, and the only available move is to the
origin (0,0), so Player 1 loses this play of the game.

\bparts 

\ppart\label{winstrat} Identify a winning strategy for the first player,
and argue its correctness.  Does your strategy guarantee any bound on the
number of game moves?

\solution{The first player essentially has two winning strategies:

\noindent
{\bf Strategy 1:} The first player starts with $(1,1)$.  Then the second
player can only pick $(0,n)$ or $(n,0)$ for some $n$.  The first player
then responds with, $(n,0)$ or $(0,n)$, respectively.  By symmetry, the
first player will always have a move whenever the second player had a
move, except when the second player picks $(0,0)$ and loses.

\noindent
{\bf Strategy 2:} The second winning strategy is slightly more tricky:
The first player starts by picking $(2,0)$,\footnote{Of course,
picking $(0,2)$ would be equivalent, and the following argument will
hold for it as well, with x and y coordinates replaced} and then:
\begin{itemize}
\item
If the 2nd player picks $(0,n)$ for any $n\geq{1}$, 1st player responds with
$(1,n-1)$.
\item
If the 2nd player picks $(1,n)$ for any $n\geq{0}$, 1st player
responds with $(0,n+1)$.
\end{itemize}
The above procedure should be repeated for all consecutive moves.  Notice
that if Player 2 had a valid move, so does Player 1, unless Player 2
picked $(0,0)$ and lost.
}

\ppart Is there a winning strategy for the first player that guarantees a bound on the number of game moves?

\solution{No, because neither of the winning strategies described in the
solution to part~(\ref{winstrat}) guarantees a bound, and there are no
other winning strategies.

To see this, suppose Player 1 starts with any legal move other than the
ones above, Player 2 will be able to adopt one of the two winning
strategies for himself and win for sure:
\begin{itemize}
\item
If Player 1 picks some $(m,n)$ where $m,n\geq{1}$ and
$(m,n)\neq(1,1)$, then player 2 can pick $(1,1)$ next, and then use
the first strategy to win against Player 1.
\item
If Player 1 picks some $(0,n)$ or $(n,0)$ where $n\geq{3}$, then
Player 2 can respectively pick $(0,2)$ or $(2,0)$ next, and then use
the second strategy to win against Player 1.
\item
If Player 1 picks $(1,0)$ or $(0,1)$ then Player 2 picks the other one
and wins.
\end{itemize}
}

\ppart Prove that the game must always terminate, even if the players
conspire to choose strategies that try to keep the game going
indefinitely.

\solution{
This is a tricky problem without some hints.

\hint (1) At any point in the game, let $x_m$ be the minimum of the values of
the $x$ coordinates of any of the previous moves, and likewise, $y_m$ be
the minimum of the values of the $y$ coordinates of any of the previous
moves.  Then $x_m+y_m$ is a \emph{weakly} decreasing natural-number valued
variable.

\begin{proof}
That's because min's cannot increase as more moves are made, so neither
can their sum.
\end{proof}

\hint (2) Suppose $a$ is the least number such that a move $(x_m,a)$ has been
made, and likewise $b$ is least such that $(b,y_m)$ has been made.  Then
the only possible moves that do not decrease $x_m+y_m$ must occur in the
rectangle with corners at $(x_m,a)$ and $(b,y_m)$.

\begin{proof}
Moves North of the rectangle are not allowed because they would be
coordinatewise larger than $(x_m,a)$, moves East of the rectangle are not
allowed because they would be coordinatewise larger than $(b,y_m)$, and
moves Northeast would be bigger than both.  Moves South of the rectangle
decrease the minimum value of $y$, moves West decrease the minimum $x$,
and moves Southwest decrease both.  That leaves only moves within the
rectangle as possibly allowed moves that do not decrease $x_m+y_m$.
\end{proof}

\hint (3) Define the size of a game position to be $(x_m+y_m,k)$ where $k$ is
the number of possible moves left in the rectangle.

\begin{proof}
Now size is a decreasing variable under the lexicographic ordering on
$\naturals^2$.  Since this lexicographic order is well-founded, the size
of the states reached in any game must have a minimal value.  Such a value
must occur at a state in which the game is terminated.
\end{proof}}

\ppart Conclude that under the coordinatewise partial order, $\naturals^2$
has no infinite antichain.

\solution{
The elements of an antichain, listed in any order is an allowed sequence
of moves.  An infinite antichain would describe a nonterminating game,
contradicting the fact that the game must terminate.
}

\ppart In $\naturals^2$ under the coordinatewise partial order, describe
an antichain of size $n$, for each $n>1$.

\solution{
(0,n-1),(1,n-2),(2,n-2),\dots,(n-1,0)
}

\eparts
\end{problem}

\begin{problem} Four Students want separate assignments to four VI-A
Companies.  Here are their preference rankings:
\begin{center}
\begin{tabular}{c|c} 
Student & Companies \\ \hline
Albert:  & HP, Bellcore, AT\&T, Draper \\
Karen:     & AT\&T, Bellcore, Draper, HP \\
Eric:   & HP, Draper, AT\&T, Bellcore \\
Kilian:    & Draper, AT\&T, Bellcore, HP
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{c|c}
Company   & Students \\ \hline
AT\&T:    & Kilian, Albert, Eric, Karen \\
Bellcore: & Eric, Karen, Albert, Kilian \\
HP:   & Kilian, Eric, Albert, Karen \\
Draper:   & Karen, Kilian, Eric, Albert
\end{tabular}
\end{center}
\bparts

\ppart
Use the Mating Algorithm to find \emph{two} stable assignments of Students
to Companies.

\solution{Treat Students as Boys and the result is the following
assignment:
\begin{center}
\begin{tabular}{c|c|c} 
Student & Companies & Rank in the original list \\ \hline
Albert:  & Bellcore & 2\\
Karen:     & AT\&T & 1\\
Eric:   & HP & 1\\
Kilian:    & Draper &1
\end{tabular}
\end{center}

Treat Companies as Boys and the result is the following assignment:
\begin{center}
\begin{tabular}{c|c|c}
Company & Students & Rank in the original list\\ \hline
AT\&T:    & Albert & 2\\
Bellcore: & Karen & 2\\
HP:   & Eric & 2\\
Draper:   & Kilian & 2
\end{tabular}
\end{center}
}

\ppart Describe a simple procedure to determine whether any given
stable marriage problem has a unique solution, \ie only one possible
stable marriage assignment.

\solution{
See if the Mating algorithm with Boys as suitors yields the same solution
as the algorithm with Girls as suitors.  These two marriage assignments
are boy-optimal and girl-optimal, respectively, so they agree iff there is
a unique solution.
}
\eparts

\end{problem}



%% source: Fall99 Q2, prob 4, Final exam Fall02
%% topics: {Graphs, Trees, State Machines, Counting, Well-order}

\begin{problem}

Given a simple graph $G$, we apply the following operation to the
graph: 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 or, there is no path from $u$ to $v$; in which case, add the edge
$\set{u,v}$.
\end{enumerate}

We 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$.  The start state
is $G$, and the final states are the graphs on which no operation is
possible.

\bparts

\ppart 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 \label{derived} For any state, $G'$, let $e$ be the number of
edges in $G'$, $c$ be the number of connected components it has, and $s$
be the number of simple cycles.  For each of the derived variables below,
indicate the \emph{strongest} of the properties that it is guaranteed to
satisfy, no matter what the starting graph $G$ is.  The choices for
properties are: \emph{constant}, \emph{strictly increasing},
\emph{strictly decreasing}, \emph{weakly increasing}, \emph{weakly
decreasing}, \emph{none of these}.  The derived variables are
 
\begin{enumerate}
%%\item[(i)] $e$ \hfill\brule{2in}\solution{none of these}
%%\item[(ii)] $c$ \hfill\brule{2in} \solution{weakly decreasing}
%%\item[(iii)] $s$ \hfill\brule{2in} \solution{weakly decreasing}

\item[(i)] $e-s$  \hfill\brule{2in} \solution{weakly increasing}

%\item[(i)] $c+e$ \hfill\brule{2in} \solution{weakly decreasing}

\item[(ii)] $3c + 2e$ \hfill\brule{2in} \solution{strictly decreasing}

\item[(iii)] $c+s$ \hfill\brule{2in} \solution{strictly decreasing}

\item[(iv)] $(c,e)$, partially ordered coordinatewise \hfill\brule{2in}
\solution{weakly decreasing}

\item[(v)] $(c,e)$, ordered lexicographically \hfill\brule{2in}
\solution{strictly decreasing}

\end{enumerate}


\ppart Choose a derived variable from above and prove that it is
strictly decreasing in some well-founded partial order.  Conclude that the
procedure terminates.

\solution{
To show that the variable (ii) strictly 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 $c$. Meanwhile the 
number of edges $e$ decreases by one when an edge is deleted. Therefore
the variable $3c+2e$ decreases by $2$. The rule for adding an edge ensures 
that the number of connected components $c$ decreases by one and the number
of edges $e$ increases by one. Therefore the variable $3c+2e$ decreases by
$1$.

To show that the variable (iii) strictly decreases, note that the rule for
deleting an edge ensures that the number of connected components $c$ 
does not change and the number of simple cycles $s$ decreases by $n$, 
where $n \geq 1$. Therefore the variable $c+s$ decreases by $n$. The rule for 
adding an edge ensures that the number of connected components $c$ decreases
by one and the number of simple cycles $s$ does not change. Therefore the 
variable $c+s$ decreases by one.

To show that the lexicographically ordered $(c,e)$ strictly decreases, 
note that the rule for deleting an edge ensures that the number of connected components
$c$ does not change and the number of edges $e$ decreases by one.
The rule for adding an edge ensures that the number of connected components $c$
decreases by one.}

\ppart 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{problem}

\end{document}


====================
\iffalse

\begin{problem}
Prove that the Mating Algorithm produces stable marriages.  (Don't look up
the proof in the Course Notes.)

\solution{\begin{proof}
Let Bob be some boy and Carole some girl that he does \emph{not} marry on
the last day of the Mating ritual.  We will prove that Bob and Carole are
not a rogue couple.  Since Bob was an arbitrary boy, it follows that no
boy is part of a rogue couple.  Hence the marriages on the last day are
stable.

To prove the claim, we consider two cases:

\emph{Case} 1.  Carole is not on Bob's list.  Then since invariant $P$
holds, we know that Carole prefers her husband to Bob.  So she's not going
to run off with Bob: the claim holds in this case.

\emph{Case} 2.  Otherwise, Carole is on Bob's list.  But since Bob is not
married to Carole, he must have chosen to serenade his wife instead of
Carole, so he must prefer wife.  So he's not going to run off with Carole:
the claim also holds in this case.
\end{proof}}

\end{problem}


\begin{problem}
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}

\begin{problem}
Give an example of a partial order with a \emph{unique} minim\emph{al}
element but no minim\emph{um} element.

\solution{The set of all real numbers totally ordered by $\le$ has no
minimal element.  We can regard $\le$ as a partial order on $\reals \union
\set{i}$, where $i$ is the complex number $\sqrt{-1}$, by agreeing that $i$
is not comparable to every real number.  This makes $i$ the unique minimal
element -- it's also the unique maximal element -- but there is no minimum
element.}
\end{problem
}


%Fast multiplication by adding and doubling from F97 pset4, problem 2.
%%%%%%%%%%%%%%%%%%%%%%% PROBLEM %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5

\begin{problem}
Consider the following multiplication algorithm, known as the ``Russian
peasant's multiplication'' to multiply numbers $a,b \in \naturals$.

The accumulator for the answer is register \texttt{p}; registers
\texttt{x}, \texttt{y} are for temporary storage.

\texttt{x:=}$a$; \texttt{y:=}$b$; \texttt{p:=}0;
\begin{verbatim}
Do until y=0:
 if even(y) then {x := 2x; y := y/2};
 if odd(y) then {p := p + x; x := 2x; y := (y-1)/2};
\end{verbatim}
We claim the product of $a$ and $b$ will be left in the accumulator
\texttt{p} when the procedure terminates.

Here is an example of the execution of the algorithm for $a=5, b = 9$:
\[\begin{array}{lccc}
\texttt{x}  &  \texttt{y} &   \texttt{p}\\
\hline
5 & 9 & 0\\
10 & 4 & 5\\
20 & 2 & 5\\
40 & 1 & 5\\
80 & 0 & 45
\end{array}\]

\begin{problemparts}

\problempart
Model the algorithm as a state machine.  

\solution{The state is the triple of values in \texttt{x, y}, and \texttt{p}.

There is just one start state: $(a,b,0)$.

There are two types of state transitions (even or odd) as described in the
algorithm:

If $y$ is even: $(x,y,p) \longrightarrow  (2x, y/2, p)$;

if $y$ is odd:  $(x,y,p) \longrightarrow (2x, (y-1)/2, p+x)$.
}

\problempart
Prove that it is correct using an invariant.

\solution{
To prove correctness, we show that
\begin{lemma*}
The predicate $P(x,y,p) \eqdef\quad [ab = xy+p]$ is an invariant.
\end{lemma*}

\begin{proof}
Consider a transition from $(x,y,p)$ to $(x',y',p')$ and suppose
$P(x,y,p)$ holds, that is, $ab = xy+p$.  We must prove that $P(x',y',p')$
holds, that is, $ab = xy+p$.  There are two cases based on the type of
action, \emph{even} or {\it odd}.

\emph{even}: Doubling $x$ while halving $y$ doesn't change the product
$xy$, and $p$ doesn't change.  So $x'y'+p' = xy+p = ab$.

\emph{odd}: $x' = 2x$, $y' = (y - 1)/ 2$, and $p' = p + x$.  So
\[
x'y' + p' = 2x(y - 1)/ 2 + p + x = (xy-x) + p + x = xy+p = ab.
\]
\end{proof}

Also, $P$ holds for the start state $(a,b,0)$ because $ab+0 = ab$.  So by
the Invariant Theorem, we conclude:
\begin{corollary*}
If $y=0$ in a reachable state, then $p = ab$.
\end{corollary*}

\begin{proof}
By our invariant, we have
$P(x,0,p)$, that is $x0 + p = ab$, so $x=ab$.
\end{proof}
}

\problempart Why is this algorithm guaranteed to terminate?  How many
arithmetic operations $(+, -, \times, / )$ does it perform when given
inputs $a$ and $b$?

\solution{Notice that the value of $y$ is a nonnegative integer that
decreases at every step unless it is 0: if $y$ is even, it becomes $y/2$
and if $y$ is odd, it becomes $(y-1)/2$.  So $y$ will eventually become 0,
and the algorithm must terminate.

In fact, since $y$ is a least halved each time around the loop, there are
at most $\floor{\log_2 b}+1$ loop executions, and each execution involves
1 multiply (by 2), one division (by 2), one addition, and at most one
subtraction.}

\end{problemparts}
\end{problem}


%------------------------------------------------
% source: pset4 problem2 spring98: part a is from ps4 in spring'97
% topic: buckets
% last used:

\begin{problem}You 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}

\bparts 
\ppart
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}
}

\ppart
\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 $\gcd(a,b) \divides k$.
\hint Use the fact that if $a,b$ are positive integers then there
exist integers $s,t$ such that $\gcd(a,b)=sa+tb$.

\solution{
We need to prove two facts (the ``iff'' statement has two directions):
\begin{enumerate}
\item
If $\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.  $\gcd(a,b)=sa+tb$, then
if $\gcd(a,b) \mid k $ then there exists an integer $n$ s.t. $n
* \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
$\gcd(a,b) \mid k $.

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

Let's denote $\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}
}

\iffalse

\ppart 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 $\gcd(a,b) \divides k$.

\solution{
Again, pick $s,t$ s.t. $c=\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$.
}
\fi

\eparts
\end{problem}

\fi
