\documentstyle[12pt,amstex,twoside]{article}
\input{macros-course}
\newcommand{\scomment}[1]{{\bf Comment: #1}}
\newcommand{\ignore}[1]{}
\newcommand{\bsol}{\vspace{0.2in}{\bf Solution:}}
\newcommand{\esol}{\vspace{0.13in}}

\begin{document}
\psol{4}{March 3, 1998}{}

%{\bf Reading assignment}: 6.042 Fall 97 Notes for Lectures 6 and 7.

\begin{problems}

\small

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 1
\problem{\bf [10 points]} 


Consider a robot which wanders on a plane.  Our robot can move 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)$?  Prove your answer.

\bsol

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 of every reachable state $(x,y)$ is that both $x$ and $y$
are integer multiples of ${\sqrt{2}}/{2}$.  It holds for the initial
state, and it is preserved by every move of our robot.  Therefore, 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}$,
and $\sqrt{2}$ would be a rational number.  Contradiction.

\esol


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 2: part a is from ps4 in spring'97
\problem{\bf [20 points]} 
%

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{\bf [4 points]} 

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

\bsol

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 (a,y,z) \mbox{ or } (x,b,z)$$

\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 (0,y,z) \mbox{ or } (x,0,z) $$

\item empty a bucket to the receptacle

$$ (x,y,z) \rightarrow (0,y,z+x) \mbox{ or } (x,0,z+y) $$

\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} 
(0,y+x,z) \mbox{ if } x < (b-y) \\
(x-(b-y),b,z) \mbox{ if } x \geq (b-y)
\end{array} \right.
$$
\end{enumerate}


\esol


\ppart{\bf [8 points]}\label{gcd-iff}

Prove that we can put $k\in\naturals$ gallons of water into the
receptacle using the above operations iff $\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$.

\bsol

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
if we first 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 preserved by
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, it divides every such linear
formula, and hence it divides the values of $x,y$ and $z$ after each
move.
\end{proof}
\end{enumerate}

\esol


\ppart{\bf [8 points]} 

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

\bsol

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

\esol

\eparts


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 3
\problem{\bf [25 points]} 
%

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.

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 the following 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{\bf [10 points]} Prove that any nonempty subset of
$\naturals^3$ has a least element under the above ordering.

\bsol

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}

\esol

\ppart{\bf [10 points]} Conclude that the game always terminates,
regardless of the players' strategy.

\bsol

We will show below that the measure $M(S)=(X(S),Y(S),B(S))$ is always
decreasing 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.

Let's prove that measure $M(S)$ decreases with every move.  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.  If $X(S)=X(S')$ and $Y(S)=Y(S')$,
then $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.

\esol



\ppart{\bf [5 points]} 

Does any player have a winning strategy?  Prove your answer.

\bsol

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 $(0,n)$ for some
$n$, the first player will respond with, respectively, $(n,0)$ or
$(0,n)$.  By symmetry, the first player will always have a move
whenever the second player had a move, except when the second player
picks $(0,0)$ and loses.

\noindent
{\bf Strategy 2:} The second winning strategy is slightly more tricky:
The first player starts by picking $(0,2)$,\footnote{Of course,
picking $(2,0)$ 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}

\esol

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem{\bf [45 points]} 

The Stable Marriage Problem was described in lecture.  In this problem
we generalize slightly to handle ``bachelors.''  The setup is that
there is a finite number, not necessarily equal, of men and women;
each man has a strict (no ties) ranking of \emph{some} of the women
according to his preference.  The women on a man's list are said to be
\emph{acceptable} to him.  Likewise each woman has a ranking of the
men who are acceptable to her.

A \emph{marriage set} is a bijection (matching) between a subset of the men
and a subset of the women such that each man is matched to a woman he
finds acceptable, and each woman is matched to a man she finds acceptable.
In other words, a marriage set matches up men and women as ``husband'' and
``wife'' so that each man has exactly one wife, and each woman exactly one
husband.  Moreover, each wife is on her husband's list of ranked women,
and each husband is on his wife's list of ranked men.  Men and women not
in the marriage set are called \emph{bachelors}.

A husband in a marriage set is said to be \emph{tempted} by a woman if (1) he
prefers the woman to his wife, and (2) either the woman prefers him to her own
husband, or the woman is a bachelor who finds him acceptable.  Similarly,
a wife may be tempted by a man.  A marriage set is \emph{stable} iff no
husband is tempted by any woman and no wife is tempted by any man.

\bparts

\ppart{\bf [5 points]}
For all $n>1$, describe a set of $n$ men and $m$ women for whom there is
exactly one stable marriage set in which they are all married.

\bsol

One solution is to arrange preferences so that each woman is the
first-choice of exactly one man, and that man is also her first
choice.  It's easy to see that when a man and a woman have each other
as first choice, they will be a rogue couple unless they are married.

Another solution is to have all the men rank the women in the same
order, and all the woman rank the men in the same order.  In other
words, all the lists held by the women are the same, and so are the
lists held by the men.  It is as if there was an ``objective''
ordering of both men that all women share and vice versa.  Then the
first-choice man must marry the first-choice woman, after which the
second best man must marry the second woman, and so on.  If they do
not marry in this order then we can find the rogue couple as follows:
Let's $x_1,\ldots,x_n$ be the above ordering of men and
$y_1,\ldots,y_n$ be the ordering of women.  Take the first man $x_i$
who marries out of order ($i=\min\{k\mid x_k\mbox{ not married to
}y_k\}$).  Then $x_i$ must have married ``below his rank'', i.e., he is
married to $y_j$ where $j>i$ (because each woman $y_k$ for $k<i$ must
be married to man $x_k$, or man $x_i$ would not be the first who
married out of order).  The woman $y_i$ that was ``rightly his'', must
have married some man $x_m$ who is also ``below her status''
(otherwise, $x_m$ would be a man of a higher rank than $x_i$, who also
married out of order).  Notice that $x_i$ and $y_i$ form a rogue
couple.

\esol

\eparts

We can approach the Stable Marriage Problem with Bachelors using
essentially the same protocol as in lecture (the only difference is
the italicized phrase ``\emph{from a man she finds acceptable}''
below):

\subsubsection*{The Mating Algorithm}

The mating ritual takes place over several days.  The following events
happen each day:

{\bf Morning}: Each man who has not yet crossed all the women off his
rank list, ``proposes'' to the woman he most prefers among those remaining
on his list.

{\bf Afternoon}: Each woman who receives at least one proposal \emph{from
a man she finds acceptable}, says to her favorite suitor, ``Maybe\fourdots\
Come back tomorrow.''  To the other suitors, she says, ``Cross me off your
list.''  We say that on this afternoon, the woman is \emph{engaged} to the
man to whom she said ``Maybe\dots''  (Some women may not be engaged to
anybody on a given afternoon.)

{\bf Evening}: Each man who hears a ``Cross me off\dots'' message, crosses
the woman who gave him the message off his list.

{\bf Termination condition}: The algorithm terminates on the first
afternoon when every man who proposed to a woman that morning ends up
engaged to her in the afternoon.  Then all the engaged couples get
married.

\bparts

\ppart{\bf [5 points]}
Model the problem as a state machine.  State clearly what the states and
state transitions are.  What is the start state? 

\bsol

Just like in the original mating problem from the lecture, our state
machine is ${\cal M} = (Q, q_0, \delta)$.  States $Q$ are all possible
ways of crossing off girls' names on the boys' lists.  The starting
state $q_0$ is the state with no names crossed off on any list.  The
transitions $\delta$ lead from a state with a given set of boys' lists
to a set in which some boys (possible none or all) have the same
lists, and some have lists with the first girl crossed off.  

In fact the boys whose lists remain the same are of three kinds:
\begin{itemize}
\item
Those whose current list of girls is empty.
\item
Those whose current first girl does not appear as currently first on
any other boy's list.
\item
Those whose current first girl appears on other boys lists as first,
but these other boys are either unacceptable to this girl (not on her
list of boys at all), or they have lower ranks on her list.
\end{itemize}
\noindent
While the boys whose new lists have the first girl crossed off are of
two kinds:
\begin{itemize}
\item
Those who are not ranked on the list of boys of their current first
girl (they are unacceptable to their current first girls).
\item
Those whose current first girl appears on other boys lists as first,
and one of those other boys ranks higher on this girl's list.
\end{itemize}

\esol

\ppart{\bf [8 points]}
Use derived variables to prove termination.  How long does the
protocol take to terminate?

\bsol

The same argument as in the original mating algorithm works here:

Let $f(q)$ be the number of uncrossed girl's names in state $q$.
Initially, every boy's list has at most $m$ uncrossed girl's names and
so $f(q_0) \leq mn$.  To prove that $f(q)$ is a decreasing derived
variable, we must show that for every execution $q_0, q_1, \ldots$, we
have $f(q_0) > f(q_1) > \ldots$.  For this purpose, it is sufficient
to show that $f(q) > f(q')$ for every transition $(q, q') \in \delta$.

In every transition $(q, q')$, since $q$ does not satisfy the
termination condition, we know that there is a man who proposes to
some girl on that morning and does not end up engaged to her in the
afternoon.  This could only happen if she told him ``Cross me
off\dots'' on that afternoon, and hence he will cross her off in the
evening.  But this means that $f(q)$ decreases by at least 1.

Notice also, that $f(q)\geq{0}$ for each $q$.  Therefore, since there
exists a decreasing derived variable $f(q)$ which take values in
natural numbers, starts from $f(q_0)\leq {mn}$, and is bounded from
below by $0$, the algorithm terminates within $nm$ steps.

\esol

\ppart{\bf [7 points]}
Prove that the marriage set at the end of the protocol is stable.

\bsol

Again, the argument is the same as in the original mating algorithm:
We use the same derived variables:

\begin{itemize}

\item Let $f_i(q)$ be the original rank that boy $i$ assigned to the
girl he is proposing to in state $q$.  If the boy is not proposing to
anyone, the value of the variable is $m+1$.

\item Let $g_i(q)$ be the original rank that girl $i$ assigned to the
boy to whom she says ``Maybe\dots'' in state $q$.  If nobody is
proposing to her in state $q$, then the value of the variable is
$n+1$.

\end{itemize}

To prove the stability of the marriage set, we will need the following
facts about the derived variables $f_i(q)$ and $g_i(q)$:

{\bf Facts}
{\em
\begin{enumerate}

\item 
$f_i$ is a non-decreasing derived variable.  As a boy crosses off
names, the rank of the girl he proposes to increases; that is, he is
forced to pursue girls that he ranks lower.

\item 
$f_i$ is non-skipping.  Each boy crosses off at most one name each
day.

\item 
$f_i(q_0) = 1$.  Initially, each boy proposes to his favorite gal.

\item 
The preceding two facts together with the Non-Skipping Theorem imply
that if boy $i$ marries eventually, then he must have at some point
proposed to each girl that he ranked higher than his mate.

\item 
Similarly, if boy $i$ never marries, he must have at some point
proposed to each girl on his list.

\item $g_i$ is a non-increasing derived variable.  Each girl keeps
stringing along her top choice by saying ``Maybe'' (holding $g_i$
constant) until someone better comes along (decreasing $g_i$) or until
the algorithm terminates.

\end{enumerate}
}

We now show that the algorithm produces a stable marriage set.  Assume
for the purpose of contradiction that there is a rogue couple $B - G$.
Let $G'$ be the girl that married $B$, and let $B'$ be the boy who
married $G$.

Since $B - G$ is a rogue couple, $B$ must like $G$ better than $G'$.
Fact 4 implies that $B$ proposed to $G$ first.  However, she must have
said ``Cross me off\dots'' to him.  This, together with Fact 6,
implies that $G$ found someone she likes even better than $B$.  In
particular, this implies that $G$ likes $B'$ better than $B$.  But
this contradicts the assumption that $B - G$ is a rogue couple.

\esol

\ppart{\bf [5 points]} Suppose that no person is unacceptable to more than
one person of the opposite sex.  Show that there can be a situation in
which every stable marriage set leaves two bachelors of each sex.
\hint Find a situation involving exactly two men and two women.

\bsol

For example, take two men $M1,M2$ and two women $W1,W2$, and
sadistically set their preferences as follows:
\begin{itemize}
\item M1 accepts only W1
\item M2 accepts only W2
\item W1 accepts only M2
\item W2 accepts only M1
\end{itemize}
No mutually acceptable marriage is possible, hence the only stable
marriage set is an empty set.  Since it leaves two men and two women
unmarried, it is true that every stable marriage leaves two bachelors
of each sex.

Note that even though in every scenario an empty set is a stable
marriage set which also leaves {\em all} men and women unmarried, it
is not true for every scenario that {\em every} stable marriage set
has this property.

\esol

\ppart{\bf [8 points]}
Suppose that the number of women and men is the same, and that no
person is unacceptable to more than one person of the opposite sex.
Show that the protocol leads to a stable marriage set where at most
two men are bachelors.

\bsol

We first prove a helpful fact:\\
%
{\it If a man finds a woman acceptable and vice versa, then it cannot
be that both end up as bachelors.}

\begin{proof}
Suppose for contradiction that M and W are bachelors.  If M finds W
acceptable, he is either married to her or proposed to her at some
point (facts 4 and 5 in part 4d).  Since he is a bachelor now, he must
have proposed to her at some point, and she must have rejected him.
But since M is acceptable to her, she could have rejected him only
because there was some man she was engaged to at that time.  But once
a woman is engaged to somebody, she has to marry (not necessarily the
same person, but someone).  Hence we have a contradiction.
\end{proof}

Now assume that there are at least 3 bachelors of one sex, say men.
\begin{itemize}
\item
Since the number of men is equal to the number of women, if there are
3 male bachelors, there are 3 female bachelors.
\item
Pick a bachelor woman W1 (call the other two W2 and W3).  She must be
unacceptable to at most one of the bachelors.  Call the other two
bachelors, those that find W acceptable, M2 and M3.
\item
If W1 found either M2 or M3 acceptable, then she would not not end up
a bachelor (from the fact argued above, and because both M1 and M2 are
bachelors).  So she finds them unacceptable.
\item
Since no man can be unacceptable to more than one woman, woman W2
(same holds for W3) must find both M2 and M3 acceptable.
\item
Since no woman can be unacceptable to more than one man, W2 must be
acceptable to either M2 or M3 (same for W3).  Without loss of
generality say that M2 finds W2 acceptable.
\item
By the fact argued above, it cannot be that both M2 and W2 end up as
bachelors.
\end{itemize}

\esol

\ppart{\bf [7 points]}

Let's modify the mating algorithm above by introducing the following
change to the procedure for the Afternoon events.  On each afternoon, all
the women say ``Maybe\dots'' as before, but only one woman says ``Cross me
off your list'' and she says it to only one (but any one) among the
suitors she would have said it to in the protocol above.

In particular, on each afternoon at most one ``Cross me off your
list'' is spoken.  Notice that now the state of the men is no longer
uniquely determined by which afternoon it is.  Briefly indicate
whether this refined protocol always yields a stable final marriage
set.  When there is a final marriage set, is it necessarily the same
as the one from the original protocol?

\bsol

{\bf Q:} Does the new protocol always yield stable final marriage set?
\\ 
{\bf A:} Yes.  The same argument as in part 4c applies here to show
that the new one-at-a-time protocol terminates (it runs slower, but it
terminates eventually).  And also the same argument as in part 4d
applies here to show the one-at-a-time protocol leads to a stable
marriage set.  Notice that all the facts 1-6 from part 4d are still
true in the new protocol.

{\bf Q:} Is the final marriage set of the new protocol the same as the
one from the original protocol?
\\ 
{\bf A:} Yes.  The two protocols produce exactly the same marriage
sets, because both of them lead to a marriage set which is
man-optimal.  You can show that the morning-afternoon-evening protocol
is man-optimal in the same way as it is shown in the lecture notes
(theorem 2.9) for the original mating problem from the lecture.
Moreover, the same argument applies to the one-at-at-time protocol
presented here.  Since there is exactly one man-optimal matching
(every man marries the first woman on his list), the two protocols
find the same matchings.

\ignore{
Another way to argue that the one-at-a-time matching is the same as
that produced by the morning-afternoon-evening protocol, is to show
that it does not matter in what order the simultaneously possible
crossings-out are performed.  This argument would be more complicated,
and it would involve arguing the following fact:

If at some point, woman W1 can tell man M1 to cross her off his list,
and at the same time woman W2 can tell man M2 to cross her off, then
if either of these cross-out occurs, it will still be possible to do
the other one next.

% PROF. MEYER:
%I doubt that anyone will come up with this argument, so I won't finish
%spelling it out, but if you see anyone with reasoning along the line of
%this lemma, don't assume they're off the track.
}

\esol


\eparts

\end{problems}
\end{document}
