        \problemdata       % Takes 5 *mandatory* arguments
        {buckets-recep}             % latex-friendly label for the prob.
        {state machines}  % The topic(s) of the problem content.
        {}               % Source (if known)
        {F01 PS6-3, S98 PS4-2, S97 PS4} % Usage (list ones you are aware of).
        {}        % Last revision info (author, date).


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