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

\newcommand{\lexls}{\mathrel{\prec_{\text{lex}}}}
\newcommand{\lexgr}{\mathrel{\succ_{\text{lex}}}}

\begin{document} 
\inclassproblems{4, Fri.}

\begin{problem}
Define \emph{lexicographic order}, $\lexls$, on $\naturals^2$ by the rule:
\[
(a_2,b_2) \lexls (a_1,b_1)
\]
iff
\[
a_2 < a_1 \text{  or  } [a_2 = a_1 \text{  and  } b_2 < b_1].
\]

Prove that there is \emph{no} infinite $\lexls$-decreasing sequence
\begin{equation}\label{dc}
(a_1,b_1) \lexgr (a_2,b_2) \lexgr \cdots \lexgr (a_n,b_n) \lexgr \cdots
\end{equation}

\iffalse
(It's not hard to verify that $\lexls$ is a total order, but this fact is
not needed.)
\fi

\hint Consider the smallest $a_m$.

\solution{
By contradiction.  Suppose there was such a lexicographically decreasing
sequence~(\ref{dc}).  By the Least Number Principle (LNP), the must be a
minimum value among the elements of the set $\set{a_1,a_2,\dots}$.  Also,
by definition of lexicographic order, the sequence $a_1,a_2,\dots$ is
weakly decreasing.  So if $a_m$ is the minimum value, then the sequence of
$a_i$'s is constant from the $m$th element on.

Now for $i \geq m$, we have by~(\ref{dc})
\[
(a_m,b_i) = (a_i,b_i) \lexgr (a_{i+1},b_{i+1}) = (a_m,b_{i+1})
\]
and so $b_i > b_{i+1}$ by definition of lexicographic order.  Hence,
$\set{b_m,b_{m+1},\dots}$ is an infinite set of natural numbers with no
least element, contradicting the LNP.
}

\end{problem}

\begin{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 none of the previous moves may simultaneously be below and
to the left of the current move.  That is, if $(x,y)$ is the current move
and $(x',y')$ is any previous move, then either $x<x'$ (so the previous
move is to the right the current one) or $y<y'$ (so the previous move is
above the previous one).  A player who moves to the origin $(0,0)$ is the
loser.

For example, the Player 1 might choose (5,6), after which Player 2 can
move to any point $(n,m)$ such that $n<5$ or $m<6$, for example, (4,12).
Now the players might move successsively to (4,11), (29,5), (1,1), (0,54),
(0,1).  At this point it's Player 2's turn, and he can move to to (1,0).
At this point it is Player 1's move, and the only available move is to the
origin (0,0), so Player 1 loses this play of the game.

\bparts 

\ppart\label{winstrat} Identify a winning strategy for the first player,
and argue its correctness.  Does your strategy guarantee any bound on the
number of game moves?

\solution{The first player essentially has two winning strategies:

\noindent
{\bf Strategy 1:} The first player starts with $(1,1)$.  Then the second
player can only pick $(0,n)$ or $(n,0)$ for some $n$.  The first player
then responds with, $(n,0)$ or $(0,n)$, respectively.  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 $(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}
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.
}

\instatements{\newpage}
\ppart Even if the players conspire to keep the game going as long as
possible, it will necessarily terminate.  Prove this as follows:

\item[i.] At any point in the game, let $x_m$ be the minimum of the $x$
coordinates of all of the previous moves, and likewise, $y_m$ be the
minimum of the $y$ coordinates of all of the previous moves.  Verify that
$x_m+y_m$ is a weakly decreasing natural-number valued variable.

\solution{
That's because min's cannot increase as more moves are made, so neither
can their sum.
}

\item[ii.] Suppose $a$ is the least number such that a move $(x_m,a)$ has
been made, and likewise $b$ is least such that move $(b,y_m)$ has been
made.  The \emph{bounded moves} are defined to be the possible moves in
the rectangle with corners at $(x_m,a)$ and $(b,y_m)$.  Explain why the
only moves that do not decrease $x_m+y_m$ must be bounded moves.

\solution{Moves North of the rectangle are not allowed because they would
be coordinatewise larger than $(x_m,a)$, moves East of the rectangle are
not allowed because they would be coordinatewise larger than $(b,y_m)$,
and moves Northeast would be bigger than both.  Moves South of the
rectangle decrease the minimum value of $y$, moves West decrease the
minimum $x$, and moves Southwest decrease both.  That leaves only moves
within the rectangle as possibly allowed moves that do not decrease
$x_m+y_m$.}

\item[iii.]  Define the \emph{size}, $\sigma$, of a game position to be
$(x_m+y_m,k)$ where $k$ is the number of bounded moves.  Explain why $\sigma$
is a strictly decreasing variable under lexicographic order, and use this
to conclude that the game must terminate.

\solution{(i.) and (ii.) immediately imply that $\sigma$ is a strictly
decreasing variable under lexicographic order on $\naturals^2$.  Since
lexicographic order has no infinite decreasing sequences, the sizes of all
the states reached in any game must have a minimum value.  The state with
such a minimum value must be a terminal state.}

\iffalse

\ppart \emph{(Optional)} Is there a winning strategy for the first player that
guarantees a bound on the number of game moves?

\solution{No, because neither of the winning strategies described in the
solution to part~(\ref{winstrat}) guarantees a bound, and there are no
other winning strategies.

To see this, suppose Player 1 starts with any legal move other than the
ones above, Player 2 will be able to adopt one of the two winning
strategies for himself 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}
}

\ppart Conclude that under the coordinatewise partial order, $\naturals^2$
has no infinite antichain.

\solution{
The elements of an antichain, listed in any order is an allowed sequence
of moves.  An infinite antichain would describe a nonterminating game,
contradicting the fact that the game must terminate.
}

\ppart In $\naturals^2$ under the coordinatewise partial order, describe
an antichain of size $n$, for each $n>1$.

\solution{
(0,n-1),(1,n-2),(2,n-2),\dots,(n-1,0)
}
\fi

\eparts
\end{problem}

\instatements{\newpage}
\begin{problem*}
See if you can come up with a stable marriage assignment given the
following preferences.  You are not expected to know/remember the Dating
Protocol that solves this problem and which is about to be covered in
lecture.  (And if you do remember the protocol, don't spoil your
teammates' fun by telling them.)

\begin{eqnarray*}
boys & \quad & girls \\
1 : C B E A D & \quad & A : 3 5 2 1 4 \\
2 : A B E C D & \quad & B : 5 2 1 4 3 \\
3 : D C B A E & \quad & C : 4 3 5 1 2 \\
4 : A C D B E & \quad & D : 1 2 3 4 5 \\
5 : A B D E C & \quad & E : 2 3 4 1 5
\end{eqnarray*}
\end{problem*}

\solution{See Slides 4F
(\href{http://theory.csail.mit.edu/classes/6.042/spring06/slides4f.pdf}{pdf}).}

%%F03 rec4

\instatements{\newpage}
\begin{problem} Four Students want separate assignments to four VI-A
Companies.  Here are their preference rankings:
\begin{center}
\begin{tabular}{c|c} 
Student & Companies \\ \hline
Albert:  & HP, Bellcore, AT\&T, Draper \\
Grant:     & AT\&T, Bellcore, Draper, HP \\
Sonya:   & HP, Draper, AT\&T, Bellcore \\
Christos:    & Draper, AT\&T, Bellcore, HP
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{c|c}
Company   & Students \\ \hline
AT\&T:    & Christos, Albert, Sonya, Grant \\
Bellcore: & Sonya, Grant, Albert, Christos \\
HP:   & Christos, Sonya, Albert, Grant \\
Draper:   & Grant, Christos, Sonya, Albert
\end{tabular}
\end{center}

Use the Mating Algorithm to find \emph{two} stable assignments of Students
to Companies.

\solution{Treat Students as Boys and the result is the following
assignment:
\begin{center}
\begin{tabular}{c|c|c} 
Student & Companies & Rank in the original list \\ \hline
Albert:  & Bellcore & 2\\
Grant:     & AT\&T & 1\\
Sonya:   & HP & 1\\
Christos:    & Draper &1
\end{tabular}
\end{center}

Treat Companies as Boys and the result is the following assignment:
\begin{center}
\begin{tabular}{c|c|c}
Company & Students & Rank in the original list\\ \hline
AT\&T:    & Albert & 2\\
Bellcore: & Grant & 2\\
HP:   & Sonya & 2\\
Draper:   & Christos & 2
\end{tabular}
\end{center}
}

\iffalse
\bparts
\ppart Describe a simple procedure to determine whether any given
stable marriage problem has a unique solution, \ie only one possible
stable marriage assignment.

\solution{
See if the Mating algorithm with Boys as suitors yields the same solution
as the algorithm with Girls as suitors.  These two marriage assignments
are boy-optimal and girl-optimal, respectively, so they agree iff there is
a unique solution.
}

\eparts
\fi

\end{problem}


\begin{problem}
You heard that an invariant of the Mating ritual is:
\begin{quote}
For every girl, $G$, and every boy, $B$, if $G$ is crossed off $B$'s list,
then $G$ has a favorite suitor and she prefers him over $B$.
\end{quote}

Use the invariant to prove that the Mating Algorithm produces stable
marriages.  (Don't look up the proof in the Course Notes.)

\solution{
\begin{proof}
Now let Bob be some boy and Carole be any girl that he is \emph{not}
married to on the last day of the Mating ritual.  We will prove that Bob
and Carole are not a rogue couple.  Since Bob was an arbitrary boy, it
follows that no boy is part of a rogue couple.  Hence the marriages on the
last day are stable.

To prove the claim, we consider two cases:

\emph{Case} 1.  Carole is not on Bob's list.  Then since invariant $P$
holds, we know that Carole prefers her husband to Bob.  So she's not going
to run off with Bob: the claim holds in this case.

\emph{Case} 2.  Otherwise, Carole is on Bob's list.  But since Bob is not
married to Carole, he must have chosen to serenade his wife instead of
Carole, so he must prefer his wife.  So he's not going to run off with
Carole: the claim also holds in this case.
\end{proof}}

\end{problem}


\end{document}
