\documentclass[11pt,twoside]{article}	
\usepackage{latex-macros/course}
\graphicspath{{/toc/a/class/6.042/fall02/problemrepository/figures/}}

\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

\def\lexgle{\mathrel{\preceq_{\text{glex}}}}
\def\lexg<{\mathrel{\prec_{\text{glex}}}}

%\hidesolutions
%\showsolutions

\newcommand{\meas}[1]{\mu(#1)}

\iffalse
\def\Code{%
    \leavevmode
    \old@everyhbox=\expandafter{\the\everyhbox}%
    \everyhbox=\expandafter{%
        \the\everyhbox
        \tt\frenchspacing
        \catcode`\#=12
        \global\everyhbox=\expandafter{\the\old@everyhbox}%
    }%
    \hbox
}\fi

\newcommand{\Code}[1]{\mathtt{#1}}

\renewcommand{\reading}{Week 5 Notes.}

\begin{document}

\problemset{4}


\begin{problem}
The Massachusetts Turnpike Authority is concerned about the integrity of
the new
\href{http://theory.lcs.mit.edu/classes/6.042/spring02/BrdgCrne-14.htm}
{Leonard Zakim bridge}.  Their consulting architect has warned that the
bridge may collapse if more than 500 cars are on it at the same time.  The
Authority has also been warned by their traffic consultants that the rate
of accidents from cars speeding across bridges has been increasing.

Both to lighten traffic and to discourage speeding, the Authority has
decided to make the bridge \emph{one-way} and to put tolls at \emph{both}
ends of the bride (don't laugh, this is Massachusetts).  A car pays \$3.00
at the entry toll booth and another \$3.00 at the exit toll booth.  To be
sure that there are never too many cars on the bridge, the Authority will
let a car onto the bridge only if \emph{the difference between the amount
of money currently at the entry toll booth minus the amount at the exit
toll booth is strictly less than~\$1500}.

The Authority has asked their engineering consultants to verify that this
policy will keep the number of cars from exceeding 500.  The consultants
have decided to model this scenario with a state machine whose states are
triples of natural numbers, $(A,B,C)$, where
\begin{itemize}
\item $A \in \naturals$ is an amount of money at the entry booth,
\item $B \in \naturals $ is an amount of money at the exit booth, and
\item $C \in \naturals$ is a number of cars on the bridge.
\end{itemize}
Since the toll booth collectors may need to start off with some amount of
money in order to make change, and there may also be some number of
``official'' cars already on the bridge when it is opened to the public,
the consultants must be ready to analyze the system started at \emph{any}
state, not necessarily with a start state $(0,0,0)$.

\begin{problemparts}
\problempart Give a mathematical description of the Authority's rules
for letting cars on and off the bridge by specifying a transition relation
between states of the form $(A,B,C)$ above.

\solution{
State $(A,B,C)$ goes to state
\begin{enumerate}
\item[(i)]
$(A+3,B,C+1)$, providing that $A-B<1500$.  This transition models
the case where a car enters the bridge.

\item[(ii)]
$(A,B+3,C-1)$, providing that $C\geq 1$.  This transition models
the case where a car leaves the bridge.
\end{enumerate} 

We could also have
\begin{enumerate}
\item[(iii)]
$(A+3,B+3,C)$, if $A-B<1500$ and $C\geq 1$,
\end{enumerate}
to model the case where a car enters the bridge at the same time when
another car leaves the bridge.  But it is easy to see that this special
case can be modeled with two transitions of types~(i) and ~(ii).
}
 
\problempart
Characterize each of the following derived variables
\iffalse
\[
\renewcommand{\arraystretch}{2}
\begin{array}{|c|c|} \hline
%A  		  & \qquad \\\hline % SI
A+B 		  & \qquad\qquad\\\hline % SI
A-B 		  & \\\hline % N
1501 A-B	  & \\\hline % N
3C-A            & \\\hline % ?
C-\dfrac{A}{3} - \dfrac{B}{3} &   \\\hline
C-\dfrac{A}{3} + \dfrac{B}{3} &   \\\hline
\end{array}
\]
\fi

\begin{enumerate}
\item[(i)] $A+B$
\item[(ii)] $A-B$
\item[(iii)] $1501A-B$
\item[(iv)] $3C-A$
\item[(v)] $C-\dfrac{A}{3} - \dfrac{B}{3}$
\item[(vi)] $C-\dfrac{A}{3} + \dfrac{B}{3}$
\end{enumerate}

as one of the following: 
\begin{itemize}
\item Constant, 
\item Strictly increasing, 
\item Strictly decreasing, 
\item Weakly increasing but not constant
\item Weakly decreasing but not constant
\item None of the above    
\end{itemize}

\iffalse
\begin{center}
\begin{tabular}{|ll|} \hline
constant              & C  \\  
strictly increasing   & SI \\
strictly decreasing   & SD \\
weakly increasing but not constant & WI \\
weakly decreasing but not constant & WD \\
none of the above     & N  \\\hline
\end{tabular}
\end{center}
by entering the corresponding code next to the variable.
\fi


\solution{
In every transition, at least one of $A$ and $B$ increases. So their
sum is strictly increasing, but each of $A-B$ and $1501A-B$ can
fluctuate arbitrarily.  

The differences $3C-A$ and $C-A/3-B/3$ don't change under transitions
of type~(i), but decrease under transitions of type~(ii); so they are
weakly decreasing. On the other hand, $C$ and $A/3-B/3$ simultaneously
increase (when a car enters the bridge) or decrease (on exit) by~1,
which makes their difference (last row) a constant. 

The answers are as follows:

\begin{enumerate}
\item[(i)] $A+B$: Strictly Increasing
\item[(ii)] $A-B$: None of the above
\item[(iii)] $1501A-B$: None of the above
\item[(iv)] $3C-A$: Weakly decreasing
\item[(v)] $C-\dfrac{A}{3} - \dfrac{B}{3}$: Weakly decreasing
\item[(vi)] $C-\dfrac{A}{3} + \dfrac{B}{3}$: Constant
\end{enumerate}


\iffalse
The completed table follows.
\[
\renewcommand{\arraystretch}{2}
\begin{array}{|c|c|} \hline
%A  		  & \qquad \\\hline % SI
A+B 		  & SI\\\hline % SI
A-B 		  & N \\\hline % N
1501 A-B	  & N \\\hline % N
3C-A            & WD \\\hline % ?
C-\dfrac{A}{3} - \dfrac{B}{3} & WD  \\\hline
C-\dfrac{A}{3} + \dfrac{B}{3} & C  \\\hline
\end{array}
\]
\fi
}

\problempart The engineering consultants plan to use the Invariant
Method to prove that the bridge will never collapse under the assumption
that the bridge opens to the public with no cars on it and no money at the
toll booths.  That is, the start state is $(0,0,0)$.

They realize that in such a proof, they musn't confuse the following
properties of predicates, $P$, on states:
\begin{itemize}

\item[R] $P$ happens to be true in all the states \emph{reachable} from the
start state $(0,0,0)$.

\item[I] $P$ is \emph{invariant}, that is, if $P((A,B,C))$ is true, and
there is a transition from $(A,B,C)$ to $(A',B',C')$, then $P((A',B',C'))$
is true.

\item[G] $P$ guarantees the bridge won't collapse, that is, if
$P((A,B,C))$ is true, and there is a sequence of zero or more transitions
from $(A,B,C)$ to $(A',B',C')$, then $C' \leq 500$.
\end{itemize}

For example, the predicate $[A-B \leq 1500]$ has property R, but not
property I or G because there is an (unreachable) state, namely,
$(1499,0,500)$ in which $1499-0 \leq 1500$ but this state has a
transition to $(1502,0,501)$ where the property fails and the bridge
collapses. 

Indicate for each of the following predicates, exactly which of properties
R,I, and G it has. Explain your answers.

\begin{enumerate}

\item[(i)]  \label{item1}
$C \leq 500$ 
\solution{\textbf{R}.

\textbf{R}: by~\ref{item6}.\ below;
\textbf{not I, G}: Since $(0,0,400) \to (303,0,501)$.
}

%\item \label{item2}
% $A-B\leq 1502$.\hfill\brule{1in} \vspace{0.3in}
%
%\solution{RI, not G.}

\item[(ii)] \label{item3}
$A \geq B$.
\solution{\textbf{R}.

\textbf{R}: by~\ref{item6}.\ below; 
\textbf{not I, G}: Because $(0,0,502) \to (0,3,501)$.}

\item[(iii)] \label{item4}
$A - B= 3 C$.
\solution{\textbf{IR}.
\textbf{I}: A transition can either increase both sides of
the equality by~3 (type~(i)), or decrease both sides
by~3 (type(ii)); in both cases, the transition preserves the
equality. \textbf{R}: Since it is I and it is true at the start
state. \textbf{not G}: Provides no bounds on~$C$, \eg $(1503,0,501)$
satisfies the property.}
%\instatements{\vspace{0.3in}}

\item[(iv)] \label{item5}
$A-B < 3 C$.

\solution{\textbf{I}.

\textbf{I}: As in~\ref{item4}., a transition either increases or
decreases both sides by~3, so that the inequality is
preserved. 
\textbf{not R}: Since  it is clearly  false at the start state, which
is reachable. 
\textbf{not G}: Provides no bounds on~$C$.  
}
%\instatements{\vspace{0.3in}}

\item[(v)] \label{item6}
$A-B= 3C      \;\;\land\;\;  A-B \leq 1500$.
\solution{\textbf{RIG}.

\textbf{I}: Suppose the property holds in some state, that is, $A-B=3C$
and $A-B\leq 1500$ and a transition takes us to $(A',B',C')$.  Then
$A'-B'=3C'$, as well (same argument as in~\ref{item4}.).  To see why
$A'-B'\leq 1500$ is also true, check the two cases: if $A-B=1500$, then no
more cars can enter (a type~(i) transition is not allowed), hence the only
possible next step is for a car to exit (which decreases the difference
and preserves the inequality); if $A-B<1500$, then $A-B\leq 1497$ (since
$A-B=3C$, so the difference is a multiple of~3), so no transition can
raise the difference above~1500.  In both cases, $A'-B'\leq 1500$.

\textbf{R}: Because it is I and true at the start state.

\textbf{G}: Because it is I and implies $C\leq 500$.}
%\instatements{\vspace{0.3in}}

\item[(vi)] \label{item7}
$A-B \leq 3 C     \;\;\land\;\;  C \leq 500$.
\solution{\textbf{R}.

\textbf{R}:  by~\ref{item6}.\ above; 
\textbf{not I,G}: Since $(0,0,400) \to (303,0,501)$.}
\instatements{\vspace{0.3in}}

\end{enumerate}

\end{problemparts}
\end{problem}


%\begin{problemparts}

%\problempart

\begin{problem}

Luke Skywalker is using a training device (like the one in Starwars I)
to develop his light-saber fencing skills.  The training device is a contraption
that in every time step makes a move in a three dimensional grid and emits a
non-lethal laser beam.  
This particular training device can only move as follows:
At every step it can move 1 unit north or south AND 1 unit east or west 
AND 1 unit up or down. 
Luke is using the Force to guide his feelings but also common sense to guard
against possible attack points.

If the device starts at position $(0,0,0)$, should Luke ever guard against an
attack coming from position $(1,1,2)$?  Prove your answer using state machines
and invariants.

{\it (Note:  There are many invariants that will work for this problem.)}



\solution{The state is the position of the device in the 3-dimensional grid described
by the vector $(x,y,z)$.  State transitions occur by adding or subtracting 1 
from each component of the vector.  The start state is $(0,0,0)$.

For the purposes of the problem it will suffice to prove the following
invariant.

$P(x,y,x) = ``y+z$ is even''.

{\bf Base case:} 
$P(0,0,0)$ is true.

{\bf Inductive step:}
Assume $P(x,y,z)$ is true in order to show that $P(x',y',z')$
is true for any next state $(x',y',z')$.

By the inductive hypothesis, $y+z$ is even. 
There are four cases.

\begin{enumerate}
\item $y' = y+1$, $z' = z+1$, therefore
   $y'+z' = (y+1)+(z+1) = y+z+2$ is even.\\
\item $y' = y+1$, $z' = z-1$, therefore
   $y'+z' = (y+1)+(z-1) = y+z$ is even.\\
\item $y' = y-1$, $z' = z+1$, therefore
   $y'+z' = (y-1)+(z+1) = y+z$ is even.\\
\item $y' = y-1$, $z' = z-1$, therefore
   $y'+z' = (y-1)+(z-1) = y+z-2$ is even.\\
\end{enumerate}


As a corollary, $(1,1,2)$ is unreachable because $1+2$ is odd.
}

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{problem}


A robot wanders on a 2-dimensional plane, starting at the origin,
$(0,0)$.
In one step, he is able to move unit distance along any diagonal line,
that is, at an angle of $\pm 45$ degrees or $\pm 135$ degrees.
\begin{problemparts}
\problempart
Describe how to model the robot's behavior as a state machine.


\solution{
The possible states are:
$Q = \reals \times \reals $

The initial state is: $Q_0 = \{(0,0)\}$

The transitions are:
$\delta \subseteq Q \times Q = $ $\{(q_1, q_2)$ such that $q_2$ is 1 unit and $\pm 45$ 
degrees or 
$\pm 135$ degrees from $q_1\} $

}


\problempart
Give an execution of the state machine that reaches the point
$(\frac{5 \sqrt{2}}{2}, \frac{-3 \sqrt{2}}{2})$.



\solution{
Starting at $(0,0)$ make the following transitions: 
\begin{enumerate}
\item $-45$ degrees: New state is $(\frac{\sqrt{2}}{2}, \frac{- \sqrt{2}}{2} )$
\item $-45$ degrees: New state is $(\frac{2 \sqrt{2}}{2}, \frac{- 2 \sqrt{2}}{2} )$
\item $-45$ degrees: New state is $(\frac{3 \sqrt{2}}{2}, \frac{- 3 \sqrt{2}}{2} )$
\item $45$ degrees: New state is $(\frac{4 \sqrt{2}}{2}, \frac{- 2 \sqrt{2}}{2} )$
\item $-45$ degrees: New state is $(\frac{5 \sqrt{2}}{2}, \frac{- 3 \sqrt{2}}{2} )$
\end{enumerate}

}

\problempart
Prove (using induction on the length of the execution) that the robot
cannot reach the point $(5,5)$. 


\solution{
We will prove a stronger theorem first and then apply it to our special
case.

\begin{theorem*} 
After any n step execution (starting at $(0,0)$), the $x$ and $y$ coordinates of
the final state are both multiples of $\frac{\sqrt{2}}{2}$.
\end{theorem*}

\begin{proof} Let $P(n)$ be the predicate that after $n$ steps, the  $x$ and
the $y$ coordinates of the current state are both multiples of 
$\frac{\sqrt{2}}{2}$.

\begin{description}\itemsep 0ex
\item[Base Case:~~] $P(0)$ is true since 
$Q_0 = \{(0,0)\}$ and $0$ is a multiple of $\frac{\sqrt{2}}{2}$.
\item[Inductive Step:~~] We must show that for any  $n\ge 0$,
$P(n) \implies P(n+1)$. We can do this by picking an arbitrary $n$ step
execution and enumerating all the possibilities for the $(n+1)$th step. 
By the inductive hypothesis, after our $n$ step execution, the current $x$ and
$y$ coordinates are both multiples of 
$\frac{\sqrt{2}}{2}$.
Therefore, we can pick integers $k$ and $j$ and call our current state:
$(\frac{k \sqrt{2}}{2} , \frac{j \sqrt{2}}{2} )$

Now there
are 4 possible transitions to the new state, $q_{n+1}$:
\[
\begin{array}{rccccccccc}
45~degrees: & q_{n+1} & = & (
\frac{k \sqrt{2}}{2} + \frac{\sqrt{2}}{2},
\frac{j \sqrt{2}}{2} + \frac{\sqrt{2}}{2}) 
& = & (
\frac{(k+1)\sqrt{2}}{2}, 
\frac{(j+1)\sqrt{2}}{2}
) \\
%
-45~degrees: & q_{n+1} & = & ( 
\frac{k \sqrt{2}}{2} + \frac{\sqrt{2}}{2},
\frac{j \sqrt{2}}{2} - \frac{\sqrt{2}}{2}) 
& = & (
\frac{(k+1)\sqrt{2}}{2}, 
\frac{(j-1)\sqrt{2}}{2}
) \\
%
135~degrees: & q_{n+1} & = & ( 
\frac{k \sqrt{2}}{2} - \frac{\sqrt{2}}{2},
\frac{j \sqrt{2}}{2} + \frac{\sqrt{2}}{2}) 
& = & (
\frac{(k-1)\sqrt{2}}{2}, 
\frac{(j+1)\sqrt{2}}{2}
) \\
%
-135~degrees: & q_{n+1} & = & ( 
\frac{k \sqrt{2}}{2} - \frac{\sqrt{2}}{2},
\frac{j \sqrt{2}}{2} - \frac{\sqrt{2}}{2}) 
& = & (
\frac{(k-1)\sqrt{2}}{2}, 
\frac{(j-1)\sqrt{2}}{2}
) \\
\end{array}
\]
In all four situations, our resulting state still satisfies the
predicate. Therefore, we have $P(n) \implies P(n+1)$.

\end{description}

Finally, since the $x$ and $y$ coordinates of any reachable state are always
multiples of
$\frac{\sqrt{2}}{2}$, $(5,5)$ is not reachable.
      
\end{proof}


}
\end{problemparts}
\end{problem}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
Consider an instance of the matching problem with $n$ boys and $n$
girls.  Call a person {\em unlucky} if he or she is matched up with
one of his or her $\floor{\frac{n}{2}}$ last choices.  In this
problem, we will prove the following: 
 
{\bf Theorem}  The matching algorithm from class never produces a
matching in which every person is unlucky.

Fix an execution of the matching algorithm.  Define the variables 
$B_i, G_i, i \in \{ 1, 2, \ldots, n \}$ as follows:
\begin{description}
\item $B_i = j$ if the $i$-th boy is currently courting the $j$-th girl
on his list
\item $G_i$ is the number of boys that the $i$-th girl has rejected.
\end{description}

\begin{problemparts}
\ppart
Show that $\sum_{i=1} ^n B_i - \sum_{i=1} ^n G_i$ is preserved at each
step of the matching algorithm.

\solution{
\medskip

Let $S = \sum_{i=1} ^n B_i - \sum_{i=1} ^n G_i$.  Suppose that at step
$t$, boy $b_i$ proposes to girl $g_j$.  There are three possible outcomes:

If $g_j$ has not had any previous proposals, she must accept.  In this
case, none of the $B_i$s and none of the $G_j$s change, so $S$ is preserved.

If $g_j$ rejects, then $G_j$ increases by 1, $B_i$ increases by 1, and
the other $B$s and $G$s remain the same.  $S$ is preserved again.

If $g_j$ accepts $b_i$ because she likes him better than her current
mate $b_{i'}$, then $G_j$ increases by 1, $B_{i'}$ increases by 1, and
the other $B$s and $G$s remain the same.  $S$ is preserved in this case
as well.
}

\ppart
Formulate an invariant that you can use to prove the theorem, and 
show that your invariant is correct.

\solution{
\medskip

Let $P : S = n$.  In the initial state, this is true because everyone is
courting the first girl on their list.  From part (a) it follows that
all transitions preserve the truth value of $P$.  Therefore $P$ is an
invariant.
}

\ppart
Use your invariant to prove the theorem.

\solution{
\medskip

We prove the statement by contradiction.  Consider a match M in which
every person is unlucky.  Then:
\begin{description}
\item For every $i \in \{ 1, \ldots, n \}$, 
$B_i \geq \ceil{\frac{n}{2}} + 1$, and
\item For every $i \in \{ 1, \ldots, n \}$,
$G_i \leq \floor{\frac{n}{2}} - 1$.
\end{description}

It follows that $\sum_{i=1} ^n B_i - \sum_{i=1} ^n G_i \geq 2n$.  This
violates the invariant $P$.
}


\end{problemparts}
\end{problem}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\iffalse
        \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
\href{http://theory.lcs.mit.edu/classes/6.042/fall03/handouts/ln5.pdf}{Week
5 Notes}, \S5.4).

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


\begin{problem}
Start with 102 coins on a table, 98 showing ``heads'' and 4 showing
``tails.''  There are two ways to change the coins:
\begin{enumerate}
\item[(i)] flip over any ten coins, or

\item[(ii)] let $n$ be the number of coins on the table showing heads.  Place
$n+1$ additional coins on the table, with all the new coins initially
showing tails.
\end{enumerate}

For example, you might begin by flipping nine heads and one tail,
yielding 90 heads and 12 tails, then add 91 tails, yielding 90 heads and
103 tails.



\bparts
\ppart
Model this situation as a state machine, carefully defining the set of
states, the start state and the possible state transitions.

\solution{
This can be modeled by a state machine $M=\{Q,Q_0,\delta\}$, where:\\

\begin{itemize}
\item $Q=\naturals\times\naturals$, the first integer is the number of
heads and the second integer is the number of tails;

\item  $Q_0=\{(98,4)\}$

\item  $\delta$ is given by the rule that the next state of $(h,t)$ can be
any state of the form:\\
\[\begin{array}{l}
(h-a+(10-a),t+a-(10-a)) \mbox{ where }0\leq a\leq 10,\ a\leq h,\ 10-a\leq t,\\
\mbox{or }(h,t+h+1).\\
\end{array}\]
\end{itemize}

%\vskip0.5in
%{\bf Comment:} Most students forgot to specify the range of $a$ precisely
%for the first transition.
}

\ppart Explain how to reach a state with exactly one tail showing.

\solution{
\begin{enumerate}

\item Do operation 2 three times, yielding $(98, 4+3\cdot99)= (98,301)$.

\item Repeat 30 times: Do operation 1 to flip 10 tails into heads. This
will result in the state $(398,1)$, which is the desired state.
\end{enumerate}
}

\ppart
Define the following derived variables of a state $q$:
\begin{eqnarray*}
 C(q) & \eqdef & \mbox{ the number of coins on the table},\\
 H(q) & \eqdef & \mbox{ the number of heads},\\
 T(q) & \eqdef & \mbox{ the number of tails},\\
 C_2(q) & \eqdef & \mbox{remainder}(C(q)/ 2),\\
 H_2(q) & \eqdef & \mbox{remainder}(H(q)/ 2),\\
 T_2(q) & \eqdef & \mbox{remainder}(T(q)/ 2).
\end{eqnarray*}

Which of these variables is
\begin{enumerate}

\item increasing \solution{NONE}
\item\label{ndec} nondecreasing \solution{$C(q)$, $H_2(q)$}
\item decreasing \solution{NONE}
\item constant \solution{$H_2(q)$.

%{\bf Comment:} A lot of students failed to notice that a constant variable
%is also a nondecreasing variable, and did not put $H_2(q)$ in part~\ref{ndec}.
}
\end{enumerate}


\ppart Prove that it is not possible to reach a state in which there is
exactly one head showing.

\solution{

We claimed above that $H_2(q)$ is an invariant value, that is, it does not
change under state tramsitions.  To prove this, let $(h,t)$ be a state
with $h$ even.  For the next state, we have two cases to consider:
\begin{enumerate}
\item The first operation is executed:
$(h,t)\rightarrow(h-2a+10,t+2a-10)$.  Since $-2a+10$ is even, $H_2((h,t))=
H_2(h-2a+10, t+2a-10)$.

\item The second operation is executed: $(h,t)\rightarrow(h,t+h+1)$. The
number of heads does not change in this case, so $H_2$ does not change.
\end{enumerate}
Since the initial number of heads, 98, is even, that is, $H_2((98,4))=0$,
the Invariant Method now implies that the number of heads in a reachable
state is always even.  But since one is odd, it is not possible to reach a
state in which there is exactly one head showing.

}

\eparts
\end{problem}

\begin{problem}
Define \emph{arithmetic expressions (AE's)} to be fully parenthesized
expressions in which the binary operations of plus and times are applied
to variables.  For example,
\begin{eqnarray}
\Code{(((((x \cdot) \cdot y) \cdot x) + (y \cdot (z \cdot y))) + (w + z))},\label{flat}\\
\Code{(u + (((x+x)\cdot x) \cdot (y + z)))}\label{ldapp}
\end{eqnarray}
are AE's.

An AE is \emph{flattened} when no sum in it is a multiplier.  That is, in
any product appearing within the expression, neither of the two terms
being multiplied is a sum.  For example, expression~(\ref{flat}) above is
flat, but~(\ref{ldapp}) is not.

Flat expressions could also be described as expressions in which the the
usual \emph{left-} and \emph{right-distributivity rules} are not
applicable.  These rules are:
\begin{eqnarray}
\Code{\mathit{e} \cdot (\mathit{f} + \mathit{g})} &\longrightarrow&
\Code{(\mathit{e} \cdot \mathit{f}) + (\mathit{e} \cdot \mathit{g})},\label{ld}\\
\Code{(\mathit{f} + \mathit{g}) \cdot \mathit{e}} &\longrightarrow&
\Code{(\mathit{f} \cdot \mathit{e}) + (\mathit{g} \cdot \mathit{e})}.\label{rd}
\end{eqnarray}
\emph{Applying} a rule means rewriting a subexpression which matches the
lefthand side of a rule to the form given in the righthand side.

For example, in expression~(\ref{ldapp}), the subexpression
\begin{eqnarray}\label{matchl}
\Code{((x+x)\cdot x) \cdot (y + z)}
\end{eqnarray}
matches the lefthand side of rule~(\ref{ld}) with $e \eqdef
\Code{((x+x)\cdot x)}$, $f \eqdef \Code{y}$ and $g \eqdef \Code{z}$,
so it would rewrite into
\begin{eqnarray}\label{matchr}
\Code{(((x+x)\cdot x) \cdot y) + (((x+x)\cdot x)\cdot z)}.
\end{eqnarray}
Applying rule~(\ref{ld}) to the full expression~(\ref{ldapp}) mean
replacing the subexpression~(\ref{matchl}) with~(\ref{matchr}) to obtain
\begin{eqnarray}\label{after}
\Code{(u+((((x+x)\cdot x) \cdot y) + (((x+x)\cdot x)\cdot z)))}.
\end{eqnarray}
Note that expression~(\ref{after}) contains \emph{two} products of sums
and so is not flat.  In fact, the original expression~(\ref{ldapp}) had
only one product of a sum, so~(\ref{after}) is both \emph{bigger} and
actually contains \emph{more} product-of-sums subexpressions than the
original.

Neverthless, a simple way to flatten an expression into an equivalent one
is to repeatedly apply the distributivity rules to the expression until
they are no longer applicable.  The problem is, can we be sure they will
eventually not be applicable, or could it be possible to keep applying the
rules in a ``bad'' way that keeps yielding larger, expressions
like~(\ref{after}) that are ``worse'' than the original?

It turns out that it is impossible to keep applying the distributivity
rules without eventually getting stuck at a flattened expression, no
matter what AE you start with and no matter where you apply the rules.  If
we regard AE's as states in a state machine -- with transitions given by
the distributivity rules -- then we are saying that this state machine
will \emph{terminate} starting from any state.\footnote{As a matter of
fact, the final expression at which rule application gets stuck is
uniquely determined by the initial expression being flattened -- but
that's another story.}

There is an ingenious, simple way to verify this termination
claim.  Define the measure, $\meas{h}$, of an arithmetic expression,
$g$, by recursively as follows:
\[
\meas{g} \eqdef
   \begin{cases}
      2 &\text{ if $g$ is a variable,}\\
      \meas{e} + \meas{f} + 1, &\text{ if } g= \Code{(\mathit{e} + \mathit{f})}\\
      \meas{e} \cdot \meas{f}, & \text{if } g =\Code{(\mathit{e} \cdot \mathit{f})}
   \end{cases}
\]

\bparts

\ppart Let $h$ be an AE that is not flat, and let $h'$ be the result of
applying one of the distributivity rules to $h$.  Prove that $\meas{h'} <
\meas{h}$.  Explain why termination follows immediately from this
observation.  \hint If $h$ is $\Code{\mathit{e} \cdot (\mathit{f} +
\mathit{g})}$ and $h'$ is $\Code{(\mathit{e} \cdot \mathit{f}) + (\mathit{e}
\cdot \mathit{g})}$, then you should verify that $\meas{h'} < \meas{h}$.
But the general claim does not follow \emph{solely} from this fact, since
the expression that gets rewritten may be a proper subexpression of $h$,
not the whole of $h$.

\ppart We extend the directed distributivity rules to handle arithmetic
expressions with an additional ``minus'' operator, $\Code{-}$, that takes
\emph{one} argument.  The extra rules are:
\begin{eqnarray*}
\Code{-(-\mathit{e})} & \longrightarrow & e\\
\Code{-(\mathit{f} + \mathit{g})} & \longrightarrow & \Code{(-\mathit{f}) +
(-\mathit{g})}\\
\Code{-(\mathit{f} \cdot \mathit{g})} & \longrightarrow & \Code{(-\mathit{f}) \cdot
\mathit{g}}
\end{eqnarray*}
Verify that the rewrite system consisting of the directed distributivity
rules and the three rules above is terminating on all arithmetic
expressions.
\eparts

\end{problem}


\end{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\iffalse


\begin{problem}
SOMETHING ON WELL-FOUNDED P.O.'s
\end{problem}

\begin{problem}
Consider the matching problem from lecture.

\begin{problemparts}
\ppart
For a particular value of $n$, give an example of a stable match between $n$
boys and $n$ girls where no person gets their first choice.

\solution{
Let $n=3$.  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.
}


\ppart
Can a stable match where no person gets their first choice be produced
by the matching algorithm described in class?  If yes, state an example
and show why the example works.  If not, prove using an invariant.

\solution{
Yes. For $n=4$, for boys $1, 2, 3, 4$ and the girls $a, b, c, d$, the
following preference list yields such a match (x choices don't matter):

\begin{center}
\begin{tabular}{lllll||lllll} \hline
choice& 1st& 2nd& 3rd& 4th& choice& 1st& 2nd& 3rd& 4th \\ \hline
1& a& c& x& x& a& 3& 2& 1& 4 \\
2& b& a& x& x& b& 1& 4& 3& 2 \\
3& b& d& x& x& c& x& 1& x& x \\
4& a& b& x& x& d& x& 3& x& x \\ \hline
\end{tabular}
\end{center}

The matching algorithm executes as follows:

\begin{description}
\item[Round 1] $a$ picks $1$. $b$ picks $3$. $2, 4$ are dropped.
\item[Round 2] $a$ picks $2$. $b$ picks $4$. $1, 3$ are dropped.
\item[Round 3] $c$ picks $1$. $d$ picks $3$.
\end{description}
}
\end{problemparts}
\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{problem}
Let $\preceq$ be a well-founded partial order with domain $A$.  Let $A^f$
denote the \emph{finite} sequences of elements of $A$ of positive length.
Define a relation, $\lexg<$, on $A^f$ called \emph{general lexicographic
order} as follows.

Let $s$ be a sequence in $A^f$ of length $n_s$ and likewise $t \in A^f$ of
length $n_t$.  Then $s \lexg< t$ providing $s \neq t$, and
\begin{enumerate}
\item $n_s < n_t$, or
\item $n_s = n_t$ and $s_k \prec t_k$ where $k$ is the least number
positive integer such that $s_k \neq t_k$.
\end{enumerate}

Prove that $\lexg<$ is well-founded.

\end{problem}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{problem}

Derive an example of preferences for the unisex
version of the mating problem (all boys or all girls)
which show that it is not possible to
always pair all the players so that the marriages satisfy the
stability criterion.  

{\it (Hint: 4 people is enough)}

\solution{Consider the amoebas Ambrosius (A), Bacchus (B), Cassius (C), and 
Dominicus (D) with the following preference lists.

A: (D,B,C)\\
B: (A,D,C)\\
C: (A,B,D)\\
D: (B,A,C)\\

There are three possible assignments

1) (A,B) and (C,D) is unstable because (A,D) is rogue.\\
2) (A,C) and (B,D) is unstable because (A,B) is rogue.\\
3) (A,D) and (B,C) is unstable because (B,D) is rogue.\\
}
\end{problem}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{problem}

In this problem you are asked to design a
protocol for college admissions. The protocol must have the following 
properties:  

There are $N$ students $S_1,...,S_N$ and $M$ universities $U_1,...,U_M$.  
Each student provides a preference ranking of all $M$ universities and each 
university provides a preference ranking of all $N$ students.  
For each $i$ university $U_i$ has $n_i$ slots to fill
and sum of all slots is equal to the number of students. 
That is, $\sum_{i=1}^M n_i = N$.  
The protocol should assign every student to a university so that

\begin{enumerate}

\item For each $i$ University $U_i$ gets $n_i$ students, 

\item There does not exist students $S_i, S_j$
and universities  $U_k, U_l$ where $S_i$ is assigned to
$U_k$ and $S_j$ is assigned to $U_l$, but 
$S_j$ prefers $U_k$ to $U_l$, and $U_k$ prefers $S_j$ to $S_i$.

\item The assignment algorithm should be student optimal in the sense
that every student gets their top choice among all assignments that
satisfy conditions 1 and 2 above.

\end{enumerate}

\bparts
\ppart
Model the problem as a state machine.  State clearly what the states and
state transitions are. What is the start state? 
\bigskip

We define the following protocol.

\bigskip

\begin{enumerate}
\item Each student applies to their favorite university that he/she has not yet
ruled out.

\item University $i$ says 
``maybe'' to the $n_i$ applicants with the better ranking.
(They say ``maybe'' to everyone if the have less that $n_i$ applicants).
They say ``no way'' to the rest.

\item Any students who is turned down crosses the university of his/her list.
\end{enumerate}

The state is given by a vector of $N$ arrays containing the crossed out 
universities for each student.  The preference list for each student can be
included as part of the state or can be considered as universal constants.
The state transitions are described by the universities that are crossed off
in any time steps. There is only one initial state with no names crossed off
any list.

{\bf Termination condition:} When no university has more than $n_i$ applicants,
each university accepts the remaining applicants.

\ppart
Use derived variables to prove termination.
How long does the protocol take to terminate?

\bigskip

\begin{theorem}
The algorithm terminates in at most $NM$ steps.
\end{theorem}

\begin{proof}
Define the derived variable $f:Q \rightarrow \natural$ given by

$f(q)=$ number of universities over all students' lists that are not 
crossed off.

$f$ is decreasing because at every step before termination at least 
one name is crossed of the lists.
Note that Initially no university is crossed off,
so there are a total $NM$ universities in the lists.

\begin{center}
execution time $\leq f(q_0) \leq NM$.
\end{center}

\end{proof}


\ppart
Prove that every student is assigned and every university gets the
right number of students. 

\bigskip

Define the derived variables

$f_i(q) =$ number of universities crossed out of the list of student $i$.

$g_i(q) =$ number of students currently on-hold in university $U_i$.

$r_i(q) =$ rank of worst student to whom $U_i$ says maybe.

Facts about $f_i$

1) Nondecreasing\\
2) non-skipping\\
3) $\forall i, f_i(q_0) = 0$\\
4) $f_i(q) = M$ if and only if student $S_i$ applied to every university 
and did not get accepted anywhere\\

Facts about $g_i$

5) $g_i$ is nondecreasing\\
6) $U_i$ says no if and only if $g_i(q) > n_i$\\
7) If for some $t$, $g_i(q_t)  \geq n_i$ then $g_i(q_s)  \geq n_i$\\
for every $s >t$.

Facts about $r_i$

8) $r_i$ is non-increasing.
 
\begin{theorem}
Every student is assigned and every university gets the
right number of students. 
\end{theorem}

\begin{proof}
By contradiction.
Suppose that student $S_i$ did not get assigned to any university.

Then

\begin{eqnarray*}
S_i \text{ applied to every university (fact 4)}& \rightarrow\\
\text{Every university rejected } S_i. &  \rightarrow\\
\text{Every university received at least $n_i$ applications (fact 6)} &  \rightarrow\\
\text{Every university accepted $n_i$ students (fact 7)} &  \rightarrow\\
\text{Every student got accepted}
\end{eqnarray*}

\end{proof}

\ppart
Prove that there are no assignments violating condition 2. 

\bigskip

\begin{theorem}
There does not exist students $S_i, S_j$
and universities  $U_k, U_l$ where $S_i$ is assigned to
$U_k$ and $S_j$ is assigned to $U_l$, but 
$S_j$ prefers $U_k$ to $U_l$, and $U_k$ prefers $S_j$ to $S_i$.
\end{theorem}

\begin{proof}
By contradiction.
Suppose there is a matching $(S_i,U_k)$ and $(S_j,U_l)$ but 
$S_j$ prefers $U_k$ to $U_l$, and $U_k$ prefers $S_j$ to $S_i$.

\begin{eqnarray*}
(S_j,U_l) & \rightarrow\\
\text{$S_j$ applied to $U_k$ first (fact 1)} & \rightarrow\\
\text{$U_k$ rejected $S_j$} & \rightarrow\\ 
\text{Every applicant accepted in $U_k$ has better rank that $S_j$ (fact 8)} & 
\rightarrow\\
\text{$S_i$ has better rank than $S_j$}.
\end{eqnarray*}

The last sentence contradicts the fact that $U_k$ prefers $S_j$ to $S_i$.

\end{proof}

\ppart
Prove that condition 3 holds. 

\solution{
\begin{theorem}
The assignment is student optimal.
\end{theorem}

\begin{proof}
Let $M$ be the set of all stable pairings (pairings that don't violate 
condition $2$).

By contradiction.
Assume some students doesn't get his/her optimal university from the realm of
possibility.

Let $S_i$ be the first student that gets rejected by his/her
 optimal university $U_k$, and let $C = \{ S_{j_1},\ldots,S_{j_{n_k}} \}$ be 
the set of students currently getting a ``maybe'' in $U_k$.

By fact 8, $U_k$ prefers every student in $C$ to $S_i$. 
Since $S_i$ is the first student that gets rejected by his/her
optimal university, no student in $C$ has been rejected by their optimal
university yet, so every student in $C$ likes $U_k$ at least as much as 
their optimal.

Let $L$ be a pairing in $M$ where $U_k$ accepts $S_i$, 
and some student in $C$ (say $S_j$) is accepted in $U_l$ (there must be such
a $U_l$ since $|C \cup S_i| = n_k+1$ and $U_k$ can only 
accept $n_k$ students).
 

Then $(S_j,U_k)$ violates condition $2$.

\end{proof}
}
\eparts

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
Shah Shahryar's wife betrays him with a slave and he vows revenge on all
women.  Each night, he will marry a new bride and the next morning have
her beheaded.  One night comes beautiful Sheherezade and presents the
Shah with a game:  

You have three numbers: 1, 1 and 2.  At each time, you are allowed to
replace any two numbers $x$, $y$ with $\frac{x+y}{\sqrt{2}}$,
$\frac{x-y}{\sqrt{2}}$, but you must not change your third number.  You
will win only if, using this rule, you can obtain the numbers $a$, $b$
and $c$.

\begin{problemparts}
\ppart Model Sheherezade's game as a state machine. ({\em Note}: The
representation is a little tricky because the numbers are not ordered.)

\solution{
\medskip
\begin{description}
\item $Q = \mathbb{R}^3$
\item $Q_0 = \{ (1,1,2) \}$
\item $\delta:$
$(x,y,z) \rightarrow (\frac{x+y}{\sqrt{2}},\frac{x-y}{\sqrt{2}},z)$ or
$(x,y,z) \rightarrow (x',y',z')$, where $(x', y', z')$ is a permutation
of $(x,y,z)$.
\end{description}
}

For each of the following choices of $a$, $b$ and $c$, say whether or
not the Shah can win the game.  If yes, show a sequence of winning
steps.  If no, provide a proof using an invariant.

\ppart 
$(a,b,c) = (\frac{3 \sqrt{2}}{2}, \frac{\sqrt{2} + 1}{2},
\frac{\sqrt{2} - 1}{2})$ 

\solution{
\medskip
Yes. 
$(1,1,2) \rightarrow (2,1,1) \rightarrow $
$(\frac{3 \sqrt{2}}{2}, \frac{\sqrt{2}}{2},1) \rightarrow $  
$(\frac{3 \sqrt{2}}{2}, \frac{\sqrt{2} + 1}{2}, \frac{\sqrt{2} - 1}{2})$.
}

\ppart 
$(a, b, c) = (\frac{\sqrt{3} - 1}{2}, \frac{\sqrt{3} + 1}{2}, 7)$

\solution{
\medskip
No.  The predicate

$$P(x,y,z) : x, y, z \in \{ p + q\sqrt{2} | p, q \in \mathbb{Q} \}$$

is an invariant for the state machine.  For the base case and the
permutation transitions, the claim is evident. For the transitions of
type $(x,y,z) \rightarrow (x',y',z')$ where 
$(x',y',z') = (\frac{x+y}{\sqrt{2}},\frac{x-y}{\sqrt{2}},z)$, let
$x=p+q\sqrt{2}, y=r+s\sqrt{2}, z=u+v\sqrt{2}$.  Then 
$x' = 2(q+s) + (p+r)\sqrt{2}, y' = 2(q-s) + (p-r)\sqrt{2}, z' = z$, so 
$P(x,y,z) \rightarrow P(x',y',z')$.
Since $P(\frac{\sqrt{3} - 1}{2}, \frac{\sqrt{3} + 1}{2}, 7)$ is false,
this state is not reachable.
}

\ppart 
$(a, b, c) = (1, 2, 2)$


\solution{
\medskip
No.  The predicate

$$P(x,y,z) : x^2 + y^2 + z^2 = 6$$

is an invariant for the state machine.  For the base case and the
permutation transitions, the claim is evident again.  For the
transitions of type 
$(x,y,z) \rightarrow (\frac{x+y}{\sqrt{2}},\frac{x-y}{\sqrt{2}},z)$,
we have $x^2 + y^2 + z^2 = (\frac{x+y}{\sqrt{2}})^2 +$ 
$(\frac{x-y}{\sqrt{2}})^2 + z^2$.  Since $P(1,2,2)$ does not hold, the
state $(1,2,2)$ is not reachable.
}

\end{problemparts}
\end{problem}



%\problem
% 1
% Puzzle state machine, modular arithmetic
In ancient times, the downtown section of Verona was laid out in a 1000
by 1000 meter square.  Romeo lived at grid point $(0,0)$ of the square, 
and Juliet lived at grid point $(0,1000)$.  Of course, Romeo and Juliet 
wanted to meet, at {\em exactly\/} the same point in the square.
However, both were restricted by their rather strange families to move
according to very particular rules:
Romeo could only move $3$ units, parallel to either the $x$ axis or $y$
axis or at a $45$ degree angle to both axes.
Juliet could only move $3$ units, and only parallel to either
the $x$ axis or $y$ axis.

\begin{problemparts}

\ppart
Model Romeo and Juliet and their possible moves as a (single) state
machine.  That is, define the states $Q$, the start state $Q_0$, and the
transitions $\delta$.

\solution{
\medskip
%\begin{description}
%\item $Q = \{ (R_x, R_y, J_x, J_y) | R_x, R_y, J_x, J_y \in \{ 0,
%\ldots, 1000 \} \}$, where $(R_x, R_y)$ and $(J_x, J_y)$ are the
%positions of Romeo and Juliet, respectively.
%\item $Q_0 = \{ (0, 0, 0, 1000) \}$
%\item $\delta: (R_x, R_y, J_x, J_y)\rightarrow (R_x + 3a, R_y + 3b, J_x + 3c,
%J_y + 3d))$, where \\
%$(a, b, c, d) \in \{
%(1,0,0,0),(-1,0,0,0),(0,1,0,0),(0,-1,0,0),(1,1,0,0),(1,-1,0,0),$\\
%$(-1,1,0,0),(-1,-1,0,0),(0,0,1,0),(0,0,-1,0),(0,0,0,1),(0,0,0,-1) \}$
%\end{description}

\begin{eqnarray*}
Q &=& \{ (R_x, R_y, J_x, J_y) | R_x, R_y, J_x, J_y \in \{ 0,
\ldots, 1000 \} \}, \mbox{\ where}\\
&& (R_x, R_y) \mbox{\ and\ } (J_x, J_y) \mbox{\ are the
positions of Romeo and Juliet, respectively.}\\
Q_0& =& \{ (0, 0, 0, 1000)\} \\
\delta&:& (R_x, R_y, J_x, J_y)\rightarrow (R_x + 3a, R_y + 3b, J_x + 3c,
J_y + 3d)), \mbox{\ where} \\
&&(a, b, c, d) \in \{
(1,0,0,0),(-1,0,0,0),(0,1,0,0),(0,-1,0,0),(1,1,0,0),(1,-1,0,0),\\
&&(-1,1,0,0),(-1,-1,0,0),(0,0,1,0),(0,0,-1,0),(0,0,0,1),(0,0,0,-1) \}
\end{eqnarray*}


}


\ppart 
Can Romeo and Juliet meet by some sequence of moves?  If yes, then give
such a sequence of moves.  If no, then prove formally (using an
invariant) that no sequence of moves can yield a meeting.

\solution{
\medskip
We show that for all reachable states $q = (R_x, R_y, J_x, J_y)$, 
$$R_x + R_y - J_x - J_y \equiv 2 \pmod{3}.$$
For notational convenience, let $r(q) = R_x + R_y - J_x - J_y$.  For the
only possible initial state $q_0$, $r(q_0) = -1000$, so $r(q_0) \equiv 2
\pmod{3}$.  For any transition from state $q$ to state $q'$, we note that
$r(q')-r(q)$ is always a multiple of 3. Hence $r(q') \equiv 2 \pmod{3}$
implies $r(q) \equiv 2 \pmod{3}$.  

Suppose, for a contradiction, that Romeo and Juliet 
can meet in some state $q$. That would imply that $r(q) = 0$.
However, we just showed that $r(q)$ can never be $0$, which yields a
contradiction.
}


\end{problemparts}
\end{problem}

Used in Online Tutor
\begin{problem}
The algorithm $Mark$ starts with a connected, undirected graph $G =
(V,E)$, with all edges unmarked.  Then it proceeds to mark some of the
edges, by repeatedly performing the following steps:
\begin{enumerate}
\item {\bf Choose} any edge $e \in E$ such that there is currently no path of
marked edges between the endpoints of $e$.
\item {\bf Mark} edge $e$.
\end{enumerate}
Prove that the algorithm finishes and that when it finishes, the set
of marked edges forms a spanning tree of the input graph $G$. (A {\em
spanning tree} of $G$ is a tree whose edges are a subset of the set
$E$ of edges of $G$, and that contains an edge incident on every
vertex of $G$.)

\solution{We will need to show that the marked edges form a spanning tree
of G, \ie they form an acyclic graph and touch every vertex of G),
{\em and} that the algorithm does indeed finish.

\begin{description}

\item[Marked edges form an acyclic graph:]

Use the Invariant Theorem:

{\bf Invariant:} The marked edges form an acyclic graph. 
\begin{description}
\item[Start condition:] Initial state.  
Initially all edges are unmarked, so there are no cycles consisting of
marked edges. 

\item[Step condition:] Consider a step $(q,q')$, where we assume that
there are no cycles consisting of marked edges in state $q$.  We show
that the same condition holds in state $q'$.

In this step, the algorithm marks an edge $e$ for which there was
previously no marked path between its endpoints.  This means that,
after the step, there is exactly one marked path between the endpoints
of $e$.  Thus, the new edge is not part of a cycle, in the new state
$q'$.  This means that there are still no cycles in state $q'$.
\end{description}

\item[Marked edges touch every vertex of G:] We can show this by
noticing that if $(v, w)$ is an edge in G then there is a path of
marked edges from $v$ to $w$. If there wasn't, then $(v, w)$ would
become a candidate edge because its endpoints are not connected by
marked edges. Then $(v,w)$ would itself be marked and thus $v$ and $w$
are indeed connected by marked edges.

Now we need to show that every vertex is touched by a marked edge. For
contradiction, suppose there is some vertex $v$ in G that is not
touched by any marked edges.  However, G is connected, so there must
be at least one $(v,w)$ edge in G. Since this edge exists, $v$ and $w$
must be connected by marked edges, so $v$ must indeed be touched by a
marked edge. Contradiction.

\item[Algorithm terminates:] 
This is shown because once an edge is marked, it can never be
unmarked. Since we have a finite set of edges, and every transition
necessarily marks one edge, we will eventually run out of candidate edges
and the algorithm will terminate.

%[[[We must also show that when no rule can be applied, it must be the
%case that the marked edges form a spanning tree of $G$.
%Shishir?  Prove this?  The following lines appeared in the previous
%solution, but they don't look like a convincing proof to me.
%
%``Since the for-loop loops over all the edges then all the vertices of
%$G$ (that have edges) will be contained in the forest.''
%
%Basically, we have to argue that, if we reach a point where no further
%steps are enabled (a ``final state''), then any two nodes are
%connected by some path of marked edges.
%I think that this probably will use a lemma saying, in a final state,
%if $(v,w)$ is an edge of $G$ then there is a path of marked edges from
%v to w.
%Then apply this lemma in an inductive proof to show that any two nodes
%of $G$ (which are assumed to be connected in $G$ by SOME path), are
%connected in the final state by a path of marked edges.
%Probably could avoid the induction by using some kind of transitive
%closure result.
%]]]
%
\end{description}
}

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{problem}

Consider the following procedure to compute $a^b \bmod n$.
\begin{itemize}
\item Let $\langle b_k, b_{k-1}, \ldots, b_0\rangle$ be the binary representation of $b$.
\item Do the assignment $c := 1$.
\item Do the assignment $d := a \bmod n$.
\item Do the assignment $i := k$.
\item Repeat the following steps:
\begin{itemize}
\item if $i = 0$ \textbf{return} $d$ and halt.
\item Do the assignment $i := i-1$.
\item Do the assignment $c := 2c$.
\item Do the assignment $d := (d \cdot d) \bmod n$.
\item if $b_i = 1$
\begin{itemize}
\item Do the assignment $c := c+1$.
\item Do the assignment $d := (d \cdot a) \bmod n$.
\end{itemize}
\end{itemize}
\end{itemize}

\renewcommand{\theenumi}{(\roman{enumi})}
\begin{problemparts}
\ppart Model the procedure with a state machine. 
\solution{
The states $Q$ can be represented as triples $(c, d, i) \subset
(\mathbb{N} \times \mathbb{N}\times \mathbb{N}$). The initial state
$q_0$ is $(1,a\bmod n,k)$.  
There are two possible transitions: if $b_{i-1} = 0$,
then $(c,d,i) \rightarrow (2c, d^2 \bmod n, i-1)$, else $(c,d,i)
\rightarrow (2c+1, d^2a \bmod n, i-1)$.  The terminating condition is
$i = 0$, and the machine outputs $d$. \\
}

\ppart Notice that at the begining of every iteration 
the binary representation of $c$ 
is $\langle b_k, b_{k-1}, \ldots, b_i \rangle$.
Formulate an invariant relating $a$, $b$, $c$, $d$, $i$, and $n$,  which
holds at the top of the loop. Your invariant should imply that upon
termination, $d = a^b \bmod n$.

\solution{
The invariant is expressed by the predicate $P(\cdot)$, which
takes a state of the machine as its argument: \\ $P(c,d,i)$ = ``$d =
a^c \bmod n \wedge c = \langle b_k, b_{k-1}, \ldots, b_i \rangle$'' \\
Note that if $i = 0$ and $P(c,d,i)$, then $c = b$, and therefore $d =
a^b \bmod n$. \\
}

\ppart Prove that the invariant holds. 
\solution{
$P(q_0)$ holds, since $d = a \bmod n = a^1 \bmod n = a^c \bmod n$, 
and $c = 1 = b_k$
($b_k$ must be 1, as it is the most significant bit).  If $(q, q')$ is
a valid transition, we will show that $P(q) \Rightarrow P(q')$.  For
any state $q = (c,d,i)$, $q'$ will be a state following $q$ iff either
$b_i-1 = 0$ and $q' = (2c, d^2 \bmod n, i-1)$ or $b_i-1 = 1$ and $q'=(2c+1,
d^2a \bmod n, i-1)$.  If we assume that $P(q)$ holds, \emph{i.e.} $d_0
= a^{c_0} \bmod n$ and $c_0 = \langle b_k, b_{k-1}, \ldots,
b_{i_0}\rangle$ then there are two cases to consider. In the case
$b_{i_0-1} = 0$, we have $d = d_0 \cdot d_0 \equiv a^{c_0} \cdot
a^{c_0} \equiv a^{2c_0} \equiv a^c \pmod n$ and $c = 2c_0 = \langle
b_k, \ldots, b_{i_0}, 0 \rangle$, which is $P(q')$. In the case that
$b_{i_0-1} = 1$, we have $d = d_0 \cdot d_0 \cdot a \equiv a^{c_0}
\cdot a^{c_0} \cdot a \equiv a^{2c_0+1} \equiv a^c \pmod n$ and $c =
2c_0+1 = \langle b_k, \ldots, b_{i_0}, 1 \rangle$, which is $P(q')$. 
}
\end{problemparts}
\renewcommand{\theenumi}{(\arabic{enumi})}
\end{problem}


\fi
