\documentclass[12pt]{article}
\input{macros-course}

\newcommand{\relsub}[2]{\,#1_{#2}\,}
\usepackage{hyperref}

%% Latex asks whether or not to include solutions
%\askaboutsolutions
\askaboutsolutions

\begin{document}

%% PSET 6: Computational Processes
\ifshowsolutions
  \psetsol{6}{October 17, 2001}{\stamp}
\else
  \pset{6}{October 10, 2001}{Monday 10/15, beginning of lecture}{\stamp}
\fi

\ifshowsolutions
{} %
\else
\emph{You MUST include a \textbf{collaboration statement} and your
\textbf{TA's name} on the first page of your solutions.}
\fi

\textbf{Reading:} Lecture Notes 6.

\begin{problems}

\problem A hungry ant is placed on an unbounded grid.  Each square of
the grid either contains a crumb or is empty.  The squares containing
crumbs form a path in which, except at the ends, every crumb is
adjacent to exactly two other crumbs.  The ant is placed at one end of
the path and on a square containing a crumb.  For example, the figure
below shows a situation in which the ant faces North, and there is a
trail of food leading approximately Southeast.  The ant has already
eaten the crumb upon which it was initially placed.

\bigskip
\begin{center}
\includegraphics[width=2in]{figures/ant}
\end{center}
%%\centerline{\resizebox{!}{2.0in}{\includegraphics{figs/ant.eps}}}
\bigskip

The ant can only smell food directly in front of it.  The ant can only
remember a small number of things, and what it remembers after any move
only depends on what it remembered and smelled immediately before the
move.  Based on smell and memory, the ant may choose to move forward one
square, or it may turn right or left.  It eats a crumb when it lands on
it.

% The ant sends a signal whenever it cannot smell food on all 
% four adjacent squares.

The above scenario can be nicely modelled as a state machine in which
each state is a pair consisting of the ``ant's memory'' and
``everything else,'' e.g., information about where things are on the
grid.  Work out the details of such a model state machine; design the
ant-memory part of the state machine so the ant will eat all the
crumbs on \emph{any} finite path at which it starts and then signal
when it is done.  Be sure to clearly describe the possible states,
transitions, and inputs and outputs (if any) in your model.  Briefly
explain why your ant will eat all the crumbs.

\solnospace{
If all the crumbs are placed as if ``on a string'', then the ant can
pick them all up very easily: If the ant smells no crumb in front of
it, it should turn in some fixed direction (say left), and if it does
smell a crumb, it should go forward and eat it.  Hence the ant can eat
all the crumbs of bread even if it is completely memory-less.
However, we requested that the ant-machine stops and signals {\em
done} when all the bread crumbs are eaten.  If the ant had no memory
then after eating the last crumb it would rotate indefinitely.
Therefore we should embed it with a memory of how many times it
rotated in the same spot in the search of an adjacent bread crumb.  If
the number of turns reaches four, all the bread crumbs are eaten and
the ant can signal {\em done}.  Here is the state machine:
\begin{eqnarray*}
AntMemory &=& \{0,1,2,3,4\}
\\
BoardLocation &=& \naturals \times \naturals
\\
AntDirection &=& \set{N,E,W,S}
\\
Crumbs &\subseteq& BoardLocation
\\
AntLocation &=& BoardLocation
\\
Q &=& AntMemory \times (AntLocation \times AntDirection \times
\mathcal{P}(Crumbs) )
\end{eqnarray*}

The transitions correspond to the three actions \{``go straight'',
``turn left'', ``done''\}.  We will use variables $q=(m,l,d,C)$ to
represent a state $q\in{Q}$ ($m\in{AntMemory}, l\in{AntLocation},
d\in{AntDirection}, C\in{\mathcal{P}(Crumbs)}$).  Let ${\sf Loc}(l,d)$ be a
function taking a location $l\in{AntLocation}$ and
$d\in{AntDirection}$ and returning $l'\in{AntLocation}$ s.t. $l'$ is the
location adjacent to $l$ in direction $d$.  In particular, if the ant
is in location $l$ and goes in direction $d$, it will come to location
$l'={\sf Loc}(l,d)$.  Let ${\sf Next}(d)$ be a function which picks
next direction of an ant which turns left, i.e. ${\sf Next}$ maps N to
W, W to S, S to E, and E to N.

\begin{itemize}
\item
{\sf go straight:}
$(m,l,d,C)\rightarrow(0,{\sf Loc}(l,d),d,C\setminus\{{\sf Loc}(l,d)\})$ if
${\sf Loc}(l,d)\in{C}$.
\item
{\sf turn left:} $(m,l,d,C)\rightarrow(m+1,l,{\sf Next}(d),C)$ if
${\sf Loc}(l,d)\not\in{C}$ and $m\neq{4}$.
\item
{\sf done:} $(m,l,d,C)\rightarrow(m,l,d,C)$ if
${\sf Loc}(l,d)\not\in{C}$ and $m=4$. Furthermore, the ant signals ``done''.
\end{itemize}
}

Note that the last transition is a self-loop; the ant signals done for
eternity. One could also add another end state so that the ant signals
done only once.

%------------------------------------------------
% source: source: spring00 pset4-5
% Based on spring97, handout 28, pset 9 solutions
% topic: marriage problem (simple)
% last used:

\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$.)

\solnospace{ We will need to show that the marked edges form a
spanning tree of G ({\em i.e.} 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}
}

% %------------------------------------------------
% % source: spring00 ps4-5
% % topic: algorithm correctness and termination
% % last used:

% \problem The nondeterministic algorithm $NSort$ starts with a sequence
% $S$ of $n$ distinct integers, initially in any order.  $NSort$
% describes how to sort the sequence, in place, into increasing order.
% What it does is to choose, arbitrarily, any pair of adjacent numbers
% that appear in the wrong order, that is, that form an ``inversion''..
% It corrects this inversion by interchanging these two numbers, leaving
% the rest of the sequence $S$ unchanged.  $NSort$ repeats this step
% until no further steps can be applied.

% \begin{problemparts}
% \problempart
% Model this as a state machine.

% \solnospace{
% The state is represented by a string:
% \begin{center}
% $Q = \{ x_1 x_2 x_3 \cdots x_n $ such that $x_i \in \integers$ and the 
% $x_i$ are all 
% distinct $\}$
% \end{center}

% The possible start states are any random string so:
% \[ Q_0 = Q \]
% In other words, any state can be a starting state.

% The set of transitions 
% $\delta \subseteq Q \times Q$ is:
% \begin{center}
% $\{(q_1, q_2)\}$ such that $q_2$ is exactly the same as $q_1$ except
% two adjacent positions are swapped.  In $q_1$ these positions were out
% of order (the greater one had lower index) but in $q_2$ the order is
% correct.
% \end{center}

% }

% \problempart
% Prove that $NSort$ eventually terminates with $S$ completely sorted.

% \solnospace{
% Let us define three quantities:
% \begin{description}
% \item[~$N_{total}$:] Total number of out of order pairs in the string 
% \item[~~~$N_{adj}$:] Number of out of order {\em adjacent} pairs in the string 
% \item[$N_{nonadj}$:] Number of out of order {\em non-adjacent} pairs
% in the string
% \end{description}
% Notice that since adjacent or non-adjacent is an exhaustive set of
% possibilities for a pair, for any state:
% \[N_{total} = N_{adj} + N_{nonadj}\] 
% Also, notice that all three quantities are by definition in $\naturals$.
% The following lemma is very helpful: 

% \begin{lemma}
% $N_{total} = 0 \Longleftrightarrow N_{adj} = 0$
% \end{lemma}

% \begin{proof}

% $\Longrightarrow$. For contradiction suppose $N_{adj} \neq 0$ but
% $N_{total} = 0$. Then $N_{nonadj} = - N_{adj}$. Since both $N_{adj}$
% and $N_{nonadj}$ are nonnegative, they must both be 0. Contradiction.

% $\Longleftarrow$. For contradiction, suppose $N_{adj} = 0$ but
% $N_{total} \neq 0$. Then there exists $i, j \leq n$ such that $i < j$
% and $x_i > x_j$. Let us pick $i$ and $j$ to minimize their
% difference. In other words, out of the pairs that are inverted, let's
% pick the pair that is closest.  Since $N_{adj} = 0$, these two entries
% cannot be adjacent so $j > i + 1$.  So there is some entry, $x_{i+1}$
% adjacent to $x_i$. Since no adjacent pairs are out of order, $x_i <
% x_{i+1}$. Also, since $x_i$ and $x_j$ were the closest inverted pair,
% $x_{i+1}$ and $x_j$ cannot be inverted. Therefore, $x_{i+1} <
% x_j$. This means that $x_i < x_{i+1} < x_j$ which is a contradiction.
% \end{proof}


% First, we can use this lemma to prove {\bf correctness}. That is, we
% need to show that when the algorithm terminates, the string is
% completely sorted. We know that our algorithm terminates when there
% are no adjacent inverted pairs. Applying our lemma, this means that
% there are no inverted pairs at all. A string with no inverted pairs is
% a sorted string. QED.

% Second, we can use this lemma to prove {\bf termination}. Consider the
% following facts:
% \begin{enumerate}
% \item

% $N_{total}$ decrease with every transition. {\em (Note that $N_{adj}$
% does NOT decrease with every transition.)}  We can show this by
% examining our transition.  The exchange itself decreases the number of
% inversions by one. However, it may produce ``new'' adjacent
% inversions. But the key fact is that it can form no {\em new}
% inversions. The only thing that can happen is that a previously
% non-adjacent inversion can become adjacent. This is because the only
% items that move are the ones being exchanged, and they are being
% ordered correctly. As far as all the other items in the string are
% concerned, the two items are in the same place. Thus, the total number
% of inversions decreases by 1 at every transition.

% \item

% $N_{total}$ will eventually reach 0 in any live execution. This is
% because $N_{total}$ is a nonnegative integer by definition. By the
% well ordering principle, and the fact that it is decreasing at every
% transition, it will eventually reach 0.

% \item

% When $N_{total}$ reaches 0, the algorithm will stop. We show this by
% applying our lemma. If $N_{total} = 0$ then $N_{adj} = 0$ so the
% algorithm terminates by definition.
% \end{enumerate}

% Thus the algorithm will terminate. Also, at termination, $N_{total} =
% N_{adj} = 0$ so the string is sorted.

% }

%% OMITTED BECAUSE WE ARE NOT COVERING TIME BOUNDS
% \problempart (*) Give a good upper bound on the number of steps that
% $NSort$ can take until it terminates.

% \solnospace{
% Two possibilities are:
% \begin{description}
% \item[Loose upper bound: ]

% Every item can be exchanged with every other item at most once. So for
% all $n$ items, there are $n-1$ other items that they could be
% exchanged with. So $n(n-1) = O(n^2)$ is an upper bound.

% \item[Tight upper bound: ]

% $N_{total}$ is definitely an upper bound since it decreases by 1 at
% every step until it reaches 0. Also, $N_{total}$ is upper bounded by
% the total number of combinations of elements of the string. This is
% $\left(
% \begin{array}{c} n \\ 2 \end{array} \right)$ or $\frac{n(n-1)}{2}$. Notice
% that this is the same as the loose bound except it recognizes that every
% pair in the loose bound is actually being counted twice.

% \end{description}
% }

% \problempart (*) For the special case where n = 4, give an example
% execution that takes the maximum number of steps to terminate.

% \solnospace{

% The following execution takes $\frac{n(n-1)}{2} = \frac{4*3}{2} = 6$ steps:
% \[
% \begin{array}{rccccccc}
% Start  \longrightarrow & 4 & 3 & 2 & 1 \\
% Step~1 \longrightarrow & 3 & 4 & 2 & 1 \\
% Step~2 \longrightarrow & 3 & 2 & 4 & 1 \\
% Step~3 \longrightarrow & 3 & 2 & 1 & 4 \\
% Step~4 \longrightarrow & 2 & 3 & 1 & 4 \\
% Step~5 \longrightarrow & 2 & 1 & 3 & 4 \\
% Step~6 \longrightarrow & 1 & 2 & 3 & 4 
% \end{array}
% \]

% }

%\end{problemparts}

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

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

\bparts 
\ppart
Model this scenario with a state machine.  (What are the states?  How does
a state change in response to a move?)

\solnospace{
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 $\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).

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

% \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 $\mbox{gcd}(a,b) \mid k$.

% \solnospace{
% 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$.
% }

\eparts

%------------------------------------------------------------
% source: taken from spring 98pset 6, #2
% topic:game trees
%

\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 no move may be $\geq$ to any
previous move in both coordinates.  The player who makes the $(0,0)$
move is the loser.

\bparts 

\ppart Identify a winning strategy for the first player, and argue its
correctness.

\solnospace{
The first player has two winning strategies:

\noindent
{\bf Strategy 1:} If the first player starts with $(1,1)$ then
whatever the second player picks, either $(0,n)$ or $(n,0)$ for some
$n$, the first player will respond with, respectively, $(n,0)$ or
$(0,n)$.  By symmetry, the first player will always have a valid 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}
And 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.

Furthermore, there are no other winning strategies for player 1,
because if she starts with any other legal move, player 2 will be able
to adopt either of the two winning strategies 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}
}

\eparts

At any point in the game, a valid move $(a,b)$ is said to be
\emph{bounded} iff both $a$ is bounded above by the $x$-coordinate of
some previous move and $b$ is bounded above by the $y$-coordinate of
some previous move.  For example, if the previous moves have been
$(1,3),(3,1), (2,2)$, then there are ten possible bounded moves:
$\{(1,2),(2,1),(1,1),(0,3),(0,2),(0,1),(0,0),(1,0),(2,0),(3,0)\}$.
There is also an infinite number of possible unbounded moves at this
point, namely, any move with one coordinate equal to $0$ and the other
larger than $3$.

For any state $S$ of the game after the first move, let $X(S)$ be the
minimum of the $x$-coordinates of the previous moves, $Y(S)$ be the
minimum of the $y$-coordinates, and $B(S)$ be the number of possible
bounded moves.  Define the \emph{measure}, $M(S)$, of the state to be the
triple $(X(S), Y(S), B(S))$.

Define $<$ to be the lexicographical ordering on triples of natural
numbers:
\[(x,y,k) < (x',y',k') \iff [(x< x') \vee (x= x' \wedge
y < y') \vee (x=x' \wedge y = y' \wedge k < k')\]

\bparts

\ppart Prove that any nonempty subset of
$\naturals^3$ has a least element under the above ordering.

\solnospace{
Let $S$ be some nonempty subset of $\naturals^3$.  Let
$S_x=\{x\mid\exists {y,z}\,\,(x,y,z)\in{S}\}$.  Then
$S_x\subset\naturals$, and so by the well-ordering principle, there is
a smallest element $x_{min}$ in $S_x$.  Now take a set
$S_{y}=\{y\mid\exists {z}\,\,(x_{min},y,z)\in{S}\}$.  Since
$S_{y}\subseteq\naturals$, and it is not empty, it has a smallest
element $y_{min}$.  Similarly, the set
$S_{z}=\{z\mid(x_{min},y_{min},z)\in{S}\}$ has a smallest element
$z_{min}$.

Clearly, $(x_{min},y_{min},z_{min})$ is the smallest element in $S$.
If there was some smaller element $(x',y',z')$ in $S$, then:
\begin{itemize}
\item
If $x'<x_{min}$ then $x'\neq{x_{min}}$ would be the smallest element
in $S_x$.  Impossible.
\item
If $x'=x_{min}$ and $y'<y_{min}$ then $y'\neq{y_{min}}$ would be the
smallest element in $S_{y}$.  Impossible.
\item
If $x'=x_{min}$, $y'=y_{min}$ and $z'<z_{min}$ then $z'\neq{z_{min}}$
would be the smallest element in $S_z$.  Impossible.
\end{itemize}
}

\ppart Conclude that the game always terminates,
regardless of the players' strategy.

\solnospace{
We will show below that the measure $M(S)=(X(S),Y(S),B(S))$ 
decreases with every move
according to the ordering in $\naturals^3$ defined above.
%On the other hand $M(S)$ cannot pass below $(0,0,0)$ because the
%minimum x coordinate, the minimum y coordinate and the number of
%bounded points cannot be negative.  
%Therefore the game has to
%terminate.

Assume by
contradiction that for some move leading from state $S=(x,y)$ to state
$S'=(x',y')$, we have that $M(S')\geq{M(S)}$.  There are three cases
in which ${M(S)}\leq{M(S')}$ could be true:
\begin{enumerate}
\item
$X(S)<X(S')$, which would mean that the minimum of the x-coordinates
has increased, which is impossible (the minimum of a set to which we
are adding some new element cannot increase).
\item
$X(S)=X(S')\,\wedge\,Y(S)<Y(S')$, which would mean that the minimum of
the y-coordinates has increased, which is impossible for the same
reason as above.
\item
$X(S)=X(S')\,\wedge\,Y(S)=Y(S')\,\wedge\,B(S)\leq{B(S')}$.  Let
$\{(x_1,y_1),\ldots,(x_n,y_n)\}$ be the points that were picked up to
move $S\,\rightarrow\,S'$ (i.e., the points that constitute state $S$),
and let $(x',y')$ be the new point.  As $X(S)=X(S')$ and $Y(S)=Y(S')$,
we have $x'\geq\min_i\{x_i\}\,\wedge\,y'\geq\min_i\{y_i\}$.

We first show that $(x',y')$ must be a bounded point in state $S$.
Assume otherwise.  That would mean that either $x'$ or $y'$ were not
bounded in state $S$.  Without loss of generality, assume $x'$ was not
bounded, i.e., that $x'>{x_i}$ for all $i$.  On the other hand, we
know that $y'\geq{}y_j=\min_i\{y_i\}$.  But then $y_j\leq{y'}$ and
$x_j<x'$ which would make $(x',y')$ an illegal move.  Hence $(x',y')$
must be a bounded point of state $S$.

Now we show that since $(x',y')$ is bounded in $S$, state
$S'=S\cup\{(x',y')\}$ must have fewer bounded points than $S$, i.e.,
that $B(S')<B(S)$.  This will finish the proof that
$X(S)=X(S')\,\wedge\,Y(S)=Y(S')\,\wedge\,B(S)\leq{B(S')}$ cannot be
true.  

Notice that a point $(x,y)$ is bounded in state $S=\{x_i,y_i\}$ iff it
is a valid move and $x\leq\max_S\{x_i\}$ and $y\leq\max_S\{y_i\}$.
Since, if $(x',y')$ is bounded in $S$ then the maximal x and y
coordinates do not change from $S$ to $S'$.  Consequently, if
$x\leq\max_{S'}\{x_i\}\,\wedge\,y\leq\max_{S'}\{y_i\}$ then
$x\leq\max_S\{x_i\}\,\wedge\,y\leq\max_S\{y_i\}$.  Also, if a point
$(x,y)$ is valid in $S'$, it is also valid in $S$ (it clearly follows
from the fact that $S\subset{S'}$).  From these two facts it follows
that if a point is bounded in $S'$, it is also bounded in $S$.  In
other words, the set ${\cal B}'$ of bounded points of $S'$ is a subset
of ${\cal B}$, the set of bounded points of $S$.  Since the latter is
a finite set\footnote{
%
After the first move, the set of bounded points is always finite,
because for whatever values $x_{max},y_{max}$, there are finite number
of pairs $(x,y)\in\naturals^2$ s.t. $x\leq{x_{max}}$ and
$y\leq{y_{max}}$.
%
} and ${\cal B}'\subset\{{\cal B}\setminus(x',y')\}$, it follows that
$B(S')=|{\cal B}'|<|{\cal B}|=B(S)$.
\end{enumerate}
This proves that measure $M(S)$ always decreases and hence finishes
the proof that the game always terminates.
}
\eparts
                 
%-------------------------------------------------------------
% source: Fall 2000  Problem Set 5
% topic: marriage problem, Matching, invariant

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

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

\solnospace{
\medskip
%\textbf{Solution:}

Let $S = \sum_{i=1} ^n B_i - \sum_{i=1} ^n G_i$.  We must prove that
this quantity remains constant after any transition.

Let's consider an arbitrary girl $g_j$ at some step $t$:
\begin{itemize}

\item If $g_j$ has no suitors, $G_j$ remain the same, and no $B_i$ is
involved here.  So $S$ is preserved in this case.

\item If $g_j$ has at least one suitor, then let $k$ be the number of
suitors she has.  Then she rejects the $k-1$ boys she likes least and
tells the boy she likes most to come back the next day.  So that $G_j$
increases by $k-1$ while $k-1$ $B_i$s increase by $1$ (for the rejected
boys) and one $B_i$ remains constant (for the accepted boy).  Overall,
S is preserved in this case as well.
\end{itemize}

Since this is true for an arbitrary girl, it is true for all girls at
step $t$. Each boy is courting exactly one girl, so that if we
consider all girls along with their suitors, we are automatically
considering all boys.

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

\solnospace{
\medskip
%\textbf{Solution:}
Our invariantis that the value of $S$ is always equal to the number of
boys (or girls); $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.

\solnospace{
\medskip
%\textbf{Solution:}
We prove the statement by contradiction.  Consider a match M in which
every person is unlucky.  Then, in the final state:
\begin{description}
\item For every $i \in \{ 1, \ldots, n \}$,
$B_i \geq n + 1 - \floor{\frac{n}{2}}$ ($B_i$ is matched with a girl
ranked between $n + 1 - \floor{\frac{n}{2}}$ and $n +1 - 1 =n$), and
\item For every $i \in \{ 1, \ldots, n \}$,
$G_i \leq \floor{\frac{n}{2}} - 1$, ($G_i$ has rejected less than
$\floor{\frac{n}{2}}$ boys, otherwise she would be matched with one
{\em not} within her last $\floor{\frac{n}{2}}$ choices.
\end{description}

\begin{eqnarray*}
\sum_{i=1} ^n B_i - \sum_{i=1} ^n G_i & = & 
\sum_{i=1} ^n B_i - G_i \\
& \geq & \sum_{i=1} ^n \left(n + 1 - \floor{\frac{n}{2}}\right) - \left(\floor{\frac{n}{2}} - 1\right) \\
& = & \sum_{i=1} ^n 2 + 2 \left(\frac{n}{2} - \floor{\frac{n}{2}}\right)
\end{eqnarray*}

Since $(\frac{n}{2} - \floor{\frac{n}{2}}) \geq 0$, it follows that 
$\sum_{i=1} ^n B_i - \sum_{i=1} ^n G_i \geq 2n$. \\ This
violates the invariant $P$.
}


\end{problems}
\end{document}                            




