\documentclass[11pt,twoside]{article} \usepackage{latex-macros/course}

\renewcommand{\reading}
{\href{http://theory.lcs.mit.edu/classes/6.042/spring02/handouts/lectures/ln5.pdf}
{Week 5 Notes}}

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

%\hidesolutions         
%\showsolutions

\newcommand{\sz}{\text{size}}
\def\lexle{\mathrel{\preceq_{\text{lex}}}}
\def\lex<{\mathrel{\prec_{\text{lex}}}}
\def\coordle{\mathrel{\preceq_{\text{c}}}}
\def\coord<{\mathrel{\prec_{\text{c}}}}

\begin{document}
\problemset{5}          

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

\begin{problem}
You 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?)

\solution{
The states are triples $(x,y,z)$ which give the current amount of
water in the bucket $A$, bucket $B$, and the receptacle, respectively.
The initial state is $(0,0,0)$.

The moves make the following transitions:
\begin{enumerate}
\item fill a bucket from the hose
$$
(x,y,z) \rightarrow \left \{ \begin{array}{l}
(a,y,z) \mbox{ if filling A from the hose } \\
(x,b,z) \mbox{ if filling B from the hose }
\end{array} \right.
$$

\item pour from the receptacle to a bucket until the bucket is full
or the receptacle is empty, whichever happens first
$$ 
(x,y,z) \rightarrow \left \{ \begin{array}{l} 
(a,y,z-(a-x)) \mbox{ if pouring to A and } z \geq (a-x) \\
(x+z,y,0) \mbox{ if pouring to A and } z < (a-x) \\
(x,b,z-(b-y)) \mbox{ if pouring to B and } z \geq (b-y) \\
(x,y+z,0) \mbox{ if pouring to B and } z < (b-y) 
\end{array} \right.
$$

\item empty a bucket to the drain
$$
(x,y,z) \rightarrow \left \{ \begin{array}{l}
(0,y,z) \mbox{ if emptying A to the drain } \\
(x,0,z) \mbox{ if emptying B to the drain }
\end{array} \right.
$$

\item empty a bucket to the receptacle
$$
(x,y,z) \rightarrow \left \{ \begin{array}{l}
(0,y,z+x) \mbox{ if emptying A to the receptacle } \\
(x,0,z+y) \mbox{ if emptying B to the receptacle }
\end{array} \right.
$$

\item pour from $A$ to $B$ until either $A$ is empty or $B$ is full,
whichever happens first
$$ 
(x,y,z) \rightarrow \left \{ \begin{array}{l} 
(0,y+x,z) \mbox{ if } x < (b-y) \\
(x-(b-y),b,z) \mbox{ if } x \geq (b-y)
\end{array} \right.
$$

\item pour from $B$ to $A$ until either $B$ is empty or $A$ is full,
whichever happens first
$$ 
(x,y,z) \rightarrow \left \{ \begin{array}{l} 
(x+y,0,z) \mbox{ if } y < (a-x) \\
(a,y-(a-x),z) \mbox{ if } y \geq (a-x)
\end{array} \right.
$$
\end{enumerate}
}

\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 $\gcd(a,b) \mid k $.  \hint Use
the fact that if $a,b$ are positive integers then there exist integers
$s,t$ such that $\gcd(a,b)=sa+tb$ (proven Week 5 Notes, \S5.4).

\solution{
We need to prove two facts (the ``iff'' statement has two directions):
\begin{enumerate}
\item
If $\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.  $\gcd(a,b)=sa+tb$, then
if $\gcd(a,b) \mid k $ then there exists an integer $n$ s.t. $n
 \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\abs{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
$\gcd(a,b) \mid k $.

\begin{proof}
We show that it is an invariant of our state machine that $\gcd(a,b)$ divides
$x$, $y$ and $z$.  Thus, in particular $z$ is always a multiple of $\gcd(a,b)$.

Let's denote $\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 $\gcd(a,b) \mid k$.

% \solution{
% Again, pick $s,t$ s.t. $c=\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
\end{problem}



\begin{problem}
%(Problem adapted from F97 pset 4) used again S00 ps4

The following algorithm, called the \emph{Russian peasants algorithm}, can
be used to multiply any two natural numbers $x$ and $y$ using only
addition, left bit-shift (i.e., multiply by 2) and right bit-shift (\ie
divide by 2 and drop any remainder) operations.  The answer is
accumulated in variable $a$; variables $r$ and $s$ are for temporary
storage.

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\kill
$r:=x$; \\
$s:=y$; \\
$a:=0$;\\
do until $s=0$:\\
   \>if s is even then \\
   \>\>   $r := 2r$; \\
   \>\>   $s := s/2$;\\
   \>else \\
   \>\>   $a := a + r$; \\
   \>\>   $r := 2r$; \\
   \>\>   $s := (s-1)/2$;\\
\end{tabbing}
The answer $xy$ is the value left in the accumulator $a$ when the 
procedure terminates. 

\begin{problemparts}

\problempart Model the algorithm as a state machine.  That is, define the
states $Q$, the start states $Q_0$, and the transitions.

\solution{
\begin{eqnarray*}
Q & \eqdef & \set{(r,s,a) \suchthat r,s,a,\in \naturals}\\
Q_0 & \eqdef & \set{(x,y,0)}\\
\text{transitions} & \eqdef &(r,s,a) \longrightarrow (r',s',a'),
\end{eqnarray*}
where
\begin{align*}
r' & \eqdef 2r,\\
s' & \eqdef s/2,\ a \eqdef a'   & \text{for } s \text{ even}\\
s' & \eqdef (s-1)/2,\ a' \eqdef a+r  & \text{for } s \text{ odd}.
\end{align*}
}

\problempart List the sequence of states that appears in an execution of the
algorithm for inputs $x=5$ and $y=9$.

\solution{
$(5,9,0)\rightarrow (10,4,5) \rightarrow (20,2,5) \rightarrow (40,1,5) \rightarrow (80,0,45)$
}

\problempart Find an invariant that implies the algorithm is partially
correct, that is, that $s = 0$ implies $a = xy$.

\solution{
We prove the following predicate is invariant:
\[
P(r,s,a) \eqdef\ [xy = rs+a].
\]

We need to prove that that for any states $(r,s,a)$ and $(r',s',a')$
such that $P(r,s,a,)$ holds and for which there exists a transition 
$(r,s,a) \rightarrow (r',s',a')$ that $P(r',s',a')$ also holds.
The proof is by cases based on the type of action, \emph{even} or \emph{odd}.
\begin{description}
\item[\emph{even}: ]
Doubling $r$ while halving $s$ doesn't change the product $rs$,
and $a$ doesn't change.  So $r's'+a' = rs+a = xy$.

\item[\emph{odd}: ] 
From the transition relation we know that $r' = 2r,\ s' = s - \frac12,\text{
and } a' = a + r$.  So $r's' + a' = 2r(s - \frac12) + a + r$.  Reorganizing
terms yields $r's'+a' = rs+a = xy$.
\end{description}
The invariant is proved.

Notice that $P(r,0,a) \eqdef xy = (0s)+a = a$, as needed.
}

\problempart Prove that the algorithm terminates.

\solution{We first notice that $s\geq 0$ in all states since we defined $s$ to
be a natural number. Furthermore, for $s>0$, all transitions decrease $s$ by at
least 1.  Thus, $s$ is a decreasing, natural-number-valued variable of the
state machine and, thus, the program terminates in a finite number of steps.}

\end{problemparts}
\end{problem}

\iffalse

\begin{problem}
%[[[New 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 inversions and swaps these two numbers,
leaving the rest of the sequence $S$ unchanged.  $NSort$ repeats this step
until no further inversions are found.

An inversion is a pair of integers $(a,b)$ in the sequence where $a$ comes
before $b$ in the sequence but $b < a$.  A sorted list has no inversions.
Keep in mind that $NSort$ is only allowed to choose \emph{adjacent}
inversions (the $a$ and $b$ must be adjacent in the sequence).

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

\solution{
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.

\solution{
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:
\begin{fact*}%\label{total}
\[N_{total} = N_{adj} + N_{nonadj}\] 
\end{fact*}
Also, notice that all three quantities are by definition in $\naturals$.
The following lemma is very helpful: 

\begin{lemma*}
\[
N_{total} = 0 \implies N_{adj} = 0.
\]
\end{lemma*}

\begin{proof}

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


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

\solution{
The following execution takes $\frac{n(n-1)}{2} = \frac{4\cdot 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}
\]
}

\problempart
Give a good upper bound  in terms of $n$
on the number of steps that $NSort$ can take
until it terminates. 

\solution{

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}

}

\end{problemparts}
\end{problem}
\fi

\iffalse

\begin{problem}

\textbf{Parallel Slugs}

Three slugs are gliding along on the xy-coordinate plane. Only one slug at
a time is allowed to move and a slug may only move in a direction parallel
to the line formed by the other two slugs.  The slugs do not have to move
in any particular order and on any single move, a slug can move an unlimited
amount of distance (they do not need to take turns).

Suppose the slugs initially begin at the following points.
Slug A: $(0,0)$
Slug B: $(0,5)$
Slug C: $(5,0)$

\begin{problemparts}
\problempart
Model the system as a state-machine. Keep in mind that slugs do NOT have to
stop at integer coordinates.

\problempart
Is it possible after some sequence of moves to have Slug A remain at $(0,0)$
but for Slug B and Slug C to switch positions? Specifically, is there a
sequence of transitions in the state-machine that could lead to the following
positions.

Slug A: $(0,0)$
Slug B: $(5,0)$
Slug C: $(0,5)$

If so, describe a sequence of transitions.  If not, prove why it is not possible.


\problempart
Is it possible to reach the following set of positions for any integer $x > 0$ and any $y > 0$?

Slug A: $(x,y)$
Slug B: $(x + 5,y)$
Slug C: $(x,y + 5)$

If so, prove it is possible for any $(x,y)$.  If not, provide a counter-example.


\problempart
Prove that it is impossible for the slugs to ever end up in the following
positions. Hint: Prove an invariant about the system.

Slug A: $(-3,-3)$
Slug B: $(2,-4)$
Slug C: $(1,2)$

\end{problemparts}


\end{problem}
\fi

\begin{problem}
Four VI-A students would like a position at a company.  There are four
companies, each with one position for a VI-A student.  Below are the
students' rankings of the companies and the companies' rankings of the
students.

\begin{center}
\begin{tabular}{l|c} 
Student & Ranking of Companies \\ \hline
Nikos   & Lotus, IBM, Compaq, Akamai \\
George  & Compaq, Lotus, Akamai, IBM \\
Radhika & Compaq, Lotus, IBM, Akamai\\
Tina    & Akamai, Compaq, Lotus, IBM 
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{l|c}
Company & Ranking of Students \\ \hline
Compaq  & George, Tina, Nikos, Radhika \\
Lotus   & George, Radhika, Nikos, Tina \\
IBM     & Radhika, George, Nikos, Tina \\
Akamai  & Tina, George, Radhika, Nikos
\end{tabular}
\end{center}

Based on the rankings, the VI-A office will assign one student to each
company so the assignment forms a stable marriage set.

\bparts

\ppart There are VI-A student, $S$, and a company, $C$, that would form a
rogue pair in \emph{any} assignment in which $S$ was not assigned to $C$.
Give an example of such a pair $(S,C)$, and briefly explain why your
example has this property.

\solution{Tina likes Akamai best and Akamai likes Tina best.  So these
two would be sure to prefer each other over their spouses if they were not
married, \ie they would be a rogue pair if they were not married.  George
and Compaq are another such pair.}

\ppart Verify that in this case, the Mating Algorithm yields the same
assignment whether Students are treated as Boys or as Girls.

\solution{Either way, the result is the following assignment:
\begin{center}
\begin{tabular}{l|l|} 
Student & Companies \\ \hline
Nikos  & IBM \\
George     & Compaq \\
Radhika   & Lotus\\
Tina    & Akamai
\end{tabular}
\end{center}
}

\ppart Explain why this implies that there is only one possible stable
assignment (even including possible stable assignments that may not be
produced by the Gale/Shapley Mating Algorithm).

\solution{In the student-optimal (pessimal) assignment, a student $S$,
is assigned to their most (least) preferred company, $C$, among all
possible companies they could be assigned to in a stable assignment.  So
in any stable assignment, $S$ would be to be assigned to a company they
like no worse than $C$ nor more than $C$, so they have to be assigned to
$C$ no matter what.}

\eparts
\end{problem}

\iffalse

\begin{problem}
% source: Fall 2000 Problem Set 5
% topics: Matching, intuition

Give an example of a stable match between 3 boys and 3 girls
where no person gets their first choice.

\solution{Call the boys $1, 2, 3$ and the girls $a, b, c$.  Consider
the following preference list:

\begin{center}
\begin{tabular}{llll||llll} \hline
choice& 1st& 2nd& 3rd& choice& 1st& 2nd& 3rd \\ \hline
1& a& b& c& a& 2& 3& 1 \\
2& b& c& a& b& 3& 1& 2 \\
3& c& a& b& c& 1& 2& 3 \\ \hline
\end{tabular}
\end{center}
   
The matching $(1, b), (2, c), (3, a)$ is stable even though no person
gets their first choice.  

To see the intuition behind this solution, notice first that the first
choice of any boy has that boy as her last choice and vice versa.  
Second, notice that everyone ends up with their second choice.  

Since we show a pairing where everyone has their second choice, this 
is stable because the only way to have a rogue pair is for a boy
or girl to want their first choice, but their first choice always 
likes them least so will never want to leave their current partner.  
Therefore, we end up with a stable pairing where no one gets their
first choice.}
\end{problem}
\fi

\begin{problem}
The Stable Buddy Problem is a variant of the Stable Marriage Problem
without the constraint that matched pairs must be Boy with Girl.

In contrast to the Boy-Girl Marriage Problem, there are buddy preferences
where all buddy assignments are unstable.  Give an example of four people
and their preference rankings for which there is no stable way to assign
buddies.  Explain why.

\solution{Let the buddy preferences of four men $A, B, C, D$ be
\begin{eqnarray*}
A:& B,C,D\\
B:& C,A,D\\
C:& A,B,D\\
D:& \text{any order}\\
\end{eqnarray*}


Let Y and Z be any two among $A$, $B$, and $C$, and let $X$ be the remaining one.
Notice that the first choices of $A$, $B$, $C$ are arranged in a cycle ($A$ prefers $B$,
$B$ prefers $C$, and $C$ prefers $A$), so that $X$ must be the first choice of
either $Y$ or $Z$. 

Now for any matching into pairs, let $Y$ and $Z$ be the two among $A$, $B$, $C$ who
are paired, and $X$ be the one paired with $D$.  So one of $Y$ and $Z$, say $Y$, has $X$
as his first choice.  But since $A$, $B$, and $C$ each rank $D$ last, $X$ prefers $Y$ to
his own buddy, $D$.  So $X$, $Y$ are a rogue couple.  Notice that the ranking of
$A$, $B$, and $C$ by $D$ doesn't matter.
}

\end{problem}

\begin{problem}
Here is the generalization of the ``choose-a-pair'' game from Week 5, Friday
Class Problems to ``choose-a-triple.''  The rules are:

Player 1 chooses any triple in $\naturals^3$.  Then, starting with Player
2, the players alternate moves, choosing as a move any triple, $\mathbf{t}
\in \naturals^3$, such that no previous move is $\coordle \mathbf{t}$.  A
player wins when the other player chooses the origin (0,0,0).

For example, Player 1 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 2 with only the move (0,0,0), and the game now
ends with his loss.

Prove that there is a winning strategy for the choose-a-triple game.

\solution{By the Fundamental Theorem for terminating games of perfect
information, one of the players will have a winning strategy providing no
game can continue for a infinite number of moves. 

To prove that the game always terminates, choose any well-founded total
order, $\preceq$ on the set $\naturals^3$ of possible moves.
Lexicographic order, for example, will do nicely.

At any point in the game after the first move, let $\mathbf{x}$ be the
least triple in the well-ordering such that the $x$-coordinate of
$\mathbf{x}$ is the minimum, $x_m$, of the $x$ coordinates of all the
previous moves.  Likewise for $\mathbf{y}$ and $\mathbf{z}$.  Then
$x_m + y_m + z_m$ is a \emph{weakly} decreasing natural-number valued
variable because none of the minimum values $x_m, y_m$ and $z_m$ can
increase as more moves are made, so neither can their sum.

Now the only possible moves that do not decrease $x_m+y_m+z_m$ must occur
in the six-sided trapezoidal polyhedron with corners at $\mathbf{x}$,
$\mathbf{y}$, $\mathbf{z}$.  Define $k$ to be the number of possible moves
left in the polyhedron.  In other words, $k$ is the number of points
$(x,y,z)$ where $x \ge x_m, y \ge y_m, z \ge z_m$, and $(x,y,z)$ has not
already been eliminated by a previous move.

Define the \emph{size} of a game position to be $(x_m+y_m+z_m,k)$.  Now size is a decreasing variable under the lexicographic ordering on $\naturals^2$.
Since this lexicographic order is well-founded, the size of the states
reached in any game must have a minimal value.  Such a value must occur at
a state in which the game is terminated.}

\end{problem}

\end{document}                            
