\documentstyle[12pt,amstex,twoside]{article}
\input{macros-course}
\newcommand{\scomment}[1]{{\bf Comment: #1}}
\newcommand{\ignore}[1]{}

\begin{document}
\pset{4}{February 24, 1998}{Tuesday, March 3}

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

\begin{problems}

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%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?)

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

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

\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 three possible bounded moves
$(1,1), (1,2)$ and $(2,1)$.  There is also an infinite number of
possible unbounded moves at this point, namely, any move with any
coordinate equal to $0$.

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.

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

\ppart{\bf [5 points]} 

Does any player have a winning strategy?  Prove your answer.
\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 $n$ women for whom there is
exactly one stable marriage set in which they are all married.

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

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

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

\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 a stable marriage set leaves two bachelors of each sex.
\hint Find a situation involving exactly two men and two women.

\ppart{\bf [8 points]}
Suppose 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 either all the men are married, or all the women are married, or
there are at most two bachelors of each sex.

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

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\ignore{
\problem{\bf [ points]}
 \scomment{That's too much: maybe good for recitation or for next year?}

Consider the Newton algorithm for finding a multiplicative inverse
$1/x$ of a real number $x$.  The algorithm works by iterative
approximation: We start with some guess $y_0$ for $1/x$, and we
improve it by iterating the following computation:

$$y_{i+1}\,\leftarrow\,2y_i-x(y_i)^2$$

Our aim is to approximate $1/x$ with the error of at most
$\frac{1}{2^n}$ where $n$ is a given natural number.  In other words,
we want to output a number $y$ s.t.  $|y-1/x|\leq\frac{1}{2^n}$.

Assume that $1/2 \leq x \leq 1$ and that the initial guess is
$y_0=3/2$.

How many iterations do we need?  Prove your answer.

{\it Hint: Prove that for all $i$, $|y_{i+1}-1/x| \leq (|y_i-1/x|)^2$.}
}

\end{problems}
\end{document}
