\documentstyle[11pt,twoside,amsfonts,amstex,psfig]{article}
\input{macros-course}

\newtheorem{falsethm}[theorem]{False Theorem}
%\newtheorem{proposition}[theorem]{Proposition}
%\newtheorem{method}{Method}
\newcommand{\cross}{\times}

\begin{document}

\tutn{4}{2/26/99}{February 26, 1999}

\section{Invariants}
\subsection{The Robot}

There is a robot.  He walks around on a grid and at every step he
moves 1 unit north or south {\em and} 1 unit east or west.  (Read the
last sentence again; if you do not have the robot's motion straight,
you will be lost!)  The robot starts at position $(0, 0)$.  Can the
robot reach position $(1, 0)$?

To get some intuition, we can build such a robot from soup cans and
pipe cleaners and then observe its behavior over time.  This
experiment quickly suggests that the answer to the question is ``no'',
but can we prove it?

Let's try to model the problem as a state machine and then prove a
suitable invariant.  Recall that a state machine has three parts, a
set of states $Q$, a set of start states $Q_0$, and a set of
transitions $\delta$.  To model the robot problem, we could define
these variables as follows:

\begin{eqnarray*}
Q & = & \{ (i, j) \mid i, j \in {\cal Z} \} \\
Q_0 & = & \{ (0, 0) \} \\
\delta & = & \{ (i, j) \rightarrow (i', j') \mid i' = i \pm 1, j' = j \pm 1 \}
\end{eqnarray*}

The set ${\cal Z}$ is the integers.  The problem is now to choose an
appropriate predicate $P((i, j))$ and prove that it is an invariant.
If this predicate is false for $(1, 0)$, then we will have proven the
robot can never reach $(1, 0)$.  A natural choice is to let $P((i,
j))$ be the predicate that $(i, j) \neq (1, 0)$.

Unfortunately, this is not going to work.  The Invariant Theorem
requires that we prove $P((i, j)) \Rightarrow P((i', j'))$ for all
$(i, j) \rightarrow (i', j') \in \delta$.  But this just is not true
for our choice of predicate.  For example, $(2,1) \rightarrow (1,0)
\in \delta$, but $P((2, 1))$ does not imply $P((1, 0))$, because the
former is true and the latter is false.

We need a stronger predicate.  Consulting a list of consecutive
positions of our robot gives some insight:

\[
(0, 0) \Rightarrow (-1, 1) \Rightarrow (-2, 0) \Rightarrow (-1, 1)
\Rightarrow (0, 2) \Rightarrow (1, 1) \Rightarrow \ldots
\]

The sum of the coordinates is always even!  If we can prove that this
is an invariant, then we have proven that the robot never reaches $(1,
0)$ because the sum of the coordinates at that point is odd.

\begin{theorem}
The sum of the robot's coordinates is always even.
\end{theorem}

\begin{proof}
The proof uses the Invariant Theorem.

Let $P((i, j))$ be the predicate that $i + j$ is even.

First, we must show that the predicate holds for all start states.
$P((0, 0))$ is true because $0 + 0$ is even.

Next, we must show that $P((i, j)) \Rightarrow P((i', j'))$ for all
$(i, j) \rightarrow (i', j') \in \delta$.  That is, for each
transition $(i, j) \rightarrow (i', j') \in \delta$, assume $i + j$ is
even to prove $i' + j'$ is even.  By the definition of $\delta$, $i' =
i \pm 1$ and $j' = j \pm 1$.  Therefore, $i' + j'$ is equal to $i + j
- 2$, $i + j$, or $i + j + 2$, all of which are even.
\end{proof}

\begin{corollary}
$(1, 0)$ is not reachable.
\end{corollary}
\begin{proof}
1 + 0 is odd.
\end{proof}

For a less obvious application of parity invariance, look at the ``15
puzzle'' example in Spring 98, \texttt{H19-rec4.ps}.

\subsection{Extended GCD}  This example extends the GCD example form
lecture and also establishes a very useful fact about gcd's: the gcd of
two natural numbers, $x$ and $y$, can be expressed as a linear combination
with integer coefficients of $x$ and $y$.

Given natural numbers $x,y$, the following procedure halts with the gcd of
$x$ and $y$ in register \texttt{B}, and also integer coefficients $k,l$ in
registers \texttt{K} and \texttt{L} such that
\[kx+ly=\mbox{gcd}(x,y).\]
(This procedure and its invariants are taken from Aho, Hopcroft, and
Ullman's text on algorithms.)

Inputs: $x,y \in \naturals$.\\
Registers: A,B,K,L,U,V,Q.

\begin{verbatim}
A := x; B := y; K := 0; L := 1; U := 1; V := 0; 
loop:
if B|A, then halt;
else
 Q := floor(A/B);      %% same as Q:= quotient of A divided by B
 {A := B,              %% assignments within the braces are SIMULTANEOUS
  B := A - Q * B,      %% same as B:= A (mod B)
  U := K,
  V := L,
  K := U - Q * K,
  L := V - Q * L};
goto loop;
\end{verbatim}

\begin{proof}
Note that \texttt{A, B} behave exactly as in the standard Euclidean algorithm from
lecture, except that this procedure stops one step sooner, ensuring that
$\mbox{gcd}(x,y)$ is in \texttt{B} at the end.  This procedure
also terminates for the same reason as the Euclidean algorithm: \texttt{B} (more
precisely, the contents of register \texttt{B})
decreases (fairly rapidly) each time around the loop.

The properties which are invariant at the start of the loop are:
\begin{itemize}
\item %\label{gcd}
(a)  $\mbox{gcd}(A,B) = \mbox{gcd}(x,y)$,
\item % \label{kl}
(b) $Kx+ Ly = B$, and
\item % \label{uv}
(c) $Ux+Vy = A$.
\end{itemize}
The procedure terminates when $B | A$.  At termination, invariants (a) and
(b) imply $\mbox{gcd}(x,y) = \mbox{gcd}(A,B) = B = Kx + Ly$.  So we have
the gcd in register \texttt{B} and the desired coefficients in \texttt{K},
\texttt{L}.  To verify the invariants:

Invariant (a) is the same one as for the Euclidean algorithm, which
we proved in lecture.  To check the other two invariants, note that at the
start $A=x, B=y, K=0, L=1$ so $Kx+Ly=0x+1y=y=B$ as required; also $U=1, V=0$
and $Ux+Vy= 1x+0y=x =A$ as required.

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

Now according to the procedure, $u'=k,v'=l,a'=b$, so invariant (c) holds
for $u',v',a'$ because of invariant (b) for $k,l,b$.  Also, $k'= u - qk,
l'= v - ql, b' = a - qb$ where $q = \floor{a/b}$, so
\[k'x+l'y = (u-qk)x + (v-ql)y =ux+vy - q(kx+ly) = a - qb = b',\]
and therefore invariant (b) holds for $k',l',b'$.
\end{proof}

\subsection{Another Robot}
Consider a robot which wanders on a plane.  This robot can move a unit
distance along any diagonal line (that is at an angle of $\pm 45$
degrees or $\pm 135$ degrees).  If our robot starts at point $(0,0)$,
can it ever reach the point $(1,1)$?

\emph{Solution}: It cannot reach $(1,1)$.  Let's model the robot's
movements as a state machine and find an invariant which is preserved by
every move of the robot.  The states are pairs of coordinates $(x,y)$, the
initial state is $(0,0)$, and there are four possible movements:
\[
(x,y) \leftarrow (x\pm\frac{\sqrt{2}}{2}, y\pm\frac{\sqrt{2}}{2})
\]
An invariant property of states $(x,y)$ is that both $x$ and $y$ are
integer multiples of ${\sqrt{2}}/{2}$.  This invariant is preserved by
every move of our robot.  Also the initial state (0,0) satisfies the
invarinat property.  Therefore, all reachable states satisfy the
invariant.  So the machine can never reach a state $(1,1)$, as this state
does not satisfy the invariant.  (If it did, i.e., if there was a natural
number $m$ s.t. $1=m\sqrt{2}/{2}$ then we would have that
$\sqrt{2}={2}/{m}$, implying that $\sqrt{2}$ is rational which we know it
is not.)


\section{Well-founded Orderings} 
Remember:
\begin{defin}
A poset $(P,\preceq)$
is \emph{well-founded} iff every nonempty subset $S \subseteq P$ has a
\emph{minimal element}, namely, an element $m \in S$ such that if $s
\preceq m$, then $s = m$, for all $s \in S$.
\end{defin}

\textbf{Class exercise}: Let $W$ be the set of all finite sequences of one
or more letters of the English alphabet.  Show that ordinary
``dictionary'' order on $W$ is not well-founded.
\begin{proof}
Let $w_1 \succeq w_2$ mean that the word $w_1$ comes later in the
dictionary than $w_2$.  Then
\[b \succeq ab \succeq aab \succeq aaab \succeq \dots\]
is an infinite decreasing sequence.
\end{proof}

\textbf{The following example will probably not be presented in tutorial
for lack of time, but should be studied.}

\begin{defin}
 \emph{Full lexicographic} order on $W$ is a binary relation, $\preceq_L$, on $W$.
It is determined by the rules that $a \preceq_L b$ iff, either $a$ is
shorter than $b$, or else $a$ and $b$ are the same length and $a$ precedes
$b$ in dictionary order.
\end{defin}

\begin{lemma}
$(W, \preceq_L)$ is a well-founded poset.  In fact, it is totally ordered.
\end{lemma}
\begin{proof}
It'e easy to see that $\preceq_L$ is a total order on $W$.  To show it is
well-founded, let $S$ be any nonempty set of words.  We shall show that
$S$ has a least element.

The set of lengths of words in $S$ is a nonempty set of positive integers
and so has a least element $m$.  Let $T$ be the set of words in $S$ of
length $m$.  The set of length-$m$ words over the English alphabet is a
totally ordered set under dictionary order, and so is also well-founded
becuase it is finite.  Therefore, since $T$ is nonempty, it has a least
element.  This least element of $T$ is clearly also the least element in
$S$.
\end{proof}

\iffalse
\subsection{Termination using Lexicographic Order}
INSERT A SHORT EXAMPLE HERE  -- MAYBE.
\fi

\section{Stable Marriages}
In lecture, the Gale-Shapley protocol was shown to produce a stable set of
marriages among $n$ men and $n$ women.  As specified by Gale-Shapley, the
proposals by men are made simultaneously followed by simultaneously
rejections of less than best suitors by woman, and these rounds of
simultaneous actions repeat until very woman has a single suitor.

We want to allow more freedom in when things happen.  In particular, our
protocol will have the same rules for who gets proposed to and who gets
rejection, but our protocol will move in smaller steps: only one thing may
happen at a time --- either some man proposes to a woman that he has not
previously proposed to, or some woman rejects some current suitor who is
less desirable than some other current suitor.  We claim that letting
steps get ``out of sync'' in this way makes no difference: our small step
protocol leads to exactly the same set of marriages as Gale-Shapley.

\begin{proof}
If in some state a man can propose to a some woman, and
a woman can reject some suitor, then if the man proposes first, the woman
can still reject the same suitor next, and vice-versa.  This illustrates
why the state graph for the small-step protocol has the \emph{diamond
property}, namely,
\begin{quotation}
\noindent
if $s \rightarrow t_1$ and also $s \rightarrow t_2$, then there is a state $t_3$\\
such that $t_1 \rightarrow t_3$ and $t_2 \rightarrow t_3$.  (See Figure 1.)
\end{quotation}
This implies that the state graph has the \emph{confluence property}
\begin{quotation}
\noindent
if $s \rightarrow^* t_1$ and also $s \rightarrow^* t_2$, then there is a state $t_3$\\
such that $t_1 \rightarrow^* t_3$ and $t_2 \rightarrow^* t_3$. (See Figure 2.)
\end{quotation}
where $\rightarrow^*$ indicates any number of transitions (including
none).  The proof that the diamond property implies confluence is
illustrated in Figure 3.  (A proper proof by induction is easy but
probably less informative.)  This immediately implies that all final
states must be equal.  So the unique final state must be the same as the
Gale-Shapley final state, because our small step protocol \emph{could} do
proposals and rejections in rounds like Gale-Shapley.
\end{proof}

\section{Team Problems}
\begin{problems}

\problem Stable marriages.  To seek fairer stable marriages than the
man-optimal one provided by the Gale-Shapley procedure (or the
woman-optimal one obtained by reversing gender roles) described in
lecture, we might allow both men and women to \emph{both} propose and be
proposed to.  At any stage, the men and women have a list of potential
fiance's who have not rejected them.  Each person proposes to their top
remaining choice.  Then any person with more than one suitor may reject
any of their suitors but the best.  The process continues until no more
rejections are possible.

Analyze this process.  Here are some questions to consider: is the process
guaranteed to halt?  when it halts, is everybody always married?  when it
halts, is the marriage set stable?  can it reach a halt at more than one
marriage set?

\emph{Solution} It always halts, assuming that if any rejections are
possible at a stage, then at least one occurs.  That's because, just as in
Gale-Shapley, the total length of the potential-fiance lists gets shorter
by at least one rejection at each stage.  There are small examples showing
that everything else can go wrong.

\problem
In this problem we'll examine a two-person game.  It is not one you're
likely to be familiar with because it allows an \emph{infinite number}
of different possible moves.  Here are the rules:

Player 1 chooses any integer $n\geq 1$.  Then player 2 chooses any
$n$-tuple of natural numbers.  After that, the players alternate moves,
choosing at each move any $n$-tuple of natural numbers which is NOT
coordinatewise $\geq$ any previously chosen $n$-tuple.  The game ends when
some player cannot move.

For example, player 1 might begin by choosing $n=3$.  Then player 2 might
choose the 3-tuple (8, 9, 10).  Possible subsequent choices might then be
\[
(7,8,9), (0,1,67), (83, 0,0), (1,0,0), (0,0,1) (0,1,0)
\]
This finally leaves player 1 with only the move (0,0,0), and the game ends
since no more moves are possible.

\bparts

\ppart  Suppose player 1 chooses $n=2$ and player 2 chooses the pair
(0,1).  Show that there is still no finite bound on how long the game
might continue.

\emph{Solution}: Player 1 can choose $(10^{100},0)$ for example. Then they
choose $(10^{100}-1,0),(10^{100}-2,0), \dots$.

\medskip
Although there are arbitrarily long games, it turns out that every game
must end at some point; no game can go on forever!  We'll help you to
prove this remarkable fact by developing properties of a special class of
well-founded posets.

\begin{defin}
A poset $(P,\preceq)$ is \emph{well-quasi-ordered} iff, for every infinite
sequence $p_1, p_2, \dots p_n \dots$ of elements in $P$, there are positive
integers $i<j$ such that $p_i \preceq p_j$.
\end{defin}

\ppart Prove that if $(P,\preceq)$ is well-quasi-ordered then it is
well-founded.
\begin{proof}
If it had an infinite strictly descending chain, that would be a sequence
of the kind forbidden in well-quasi-orders.
\end{proof}

\ppart Prove that if $(P,\preceq)$ is well-quasi-ordered and $S$ is a
subset of $P$, then $S$ has only a \emph{finite} number of minimal
elements.  (Remember, $m \in S$ is \emph{minimal} iff no other element of
$S$ is $\preceq m$.)
\begin{proof}
Any infinite sequence of distinct minimal elements would be a sequence of
the kind forbidden in well-quasi-orders.
\end{proof}

\ppart Prove that any infinite sequence of elements in a
well-quasi-ordered poset contains an infinite nondecreasing subsequence.
That is, if $(P,\preceq)$ is a well-quasi-ordered poset, and $p_1, p_2,
\dots p_n \dots$ is an infinite sequence of elements in $P$, then there is
an infinite sequence of integers $i_1 < i_2 < i_3< \dots$ such that
$p_{i_1} \preceq p_{i_2} \preceq p_{i_3} \preceq \dots$.  \hint Explain
why there must be a minimal element in the sequence which is $\preceq$ an
infinite number of $p_i$'s.  \textbf{If you get stuck on this part, so go
on to the next part.}

\begin{proof}
If any element occurred infinitely often, its occurrences would form the
desired nondecreasing subsequence, so we may assume that each element in the
sequence occurs only finitely often and therefore that the sequence
contains an infinite number of distinct elements.

Now every element of a well-founded poset must be $\succeq$ some minimal
element (why?).  Since there are only a finite number of minimal elements,
there must be a minimal element $p_{i_1}$ in the sequence which is
$\preceq$ an infinite subsequence of later elements.  But this subsequence
of later elements must similarly contain a minimal element $p_{i_2}$ which
is $\preceq$ an infinite subsubsequence of elements later in the
subsubsequence.  Continuing in this way we can construct the infinite
sequence $p_{i_1} \preceq p_{i_2} \preceq p_{i_3} \preceq \dots$.
\end{proof}

\ppart Prove:
\begin{lemma}\label{coord-wqo}
Suppose  $(P, \leq_P)$ and $(Q, \leq_Q)$ are well-quasi-ordered posets.
Then so is $P \cross Q$ under the coordinatewise partial order.
\end{lemma}

\begin{proof}
Let $(p_1,q_1), (p_2,q_2), \dots (p_n,q_n) \dots$ be an infinite sequence
of elements of $P \cross Q$.

Since $(P, \leq_P)$ is well-quasi-ordered, by the previous problem part,
the sequence $p_1, p_2, \dots$ must contain an infinite subsequence
$p_{i_1} \leq_P p_{i_2} \leq_P p_{i_3} \leq_P \dots$.  Now since
$(Q,\leq_Q)$ is well-quasi-ordered, for the infinite sequence $q_{i_1},
q_{i_2},q_{i_3}, \dots$ there must be positive integers $k < l$ such that
$q_{i_k} \leq_Q q_{i_l}$.  So $(p_{i_k},q_{i_k})$ is coordinatewise less
than or equal to $(p_{i_l},q_{i_l})$.
\end{proof}

\ppart Now prove that the game must end.

\begin{proof}
Just show by induction on $n\geq 1$ that $\naturals^n$ under
coordinatewise order is well-quasi-ordered.  The base case $n=1$ is
immediate, and Lemma~\ref{coord-wqo} handles the induction case.
\end{proof}

\eparts

\end{problems}

\end{document}
