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

\renewcommand{\coursecopyrightnames}
{\href{http://theory.lcs.mit.edu/~meyer}{Prof.~Albert~R.~Meyer}}

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

\def\lexle{\mathrel{\preceq_{\text{lex}}}}
\def\lex<{\mathrel{\prec_{\text{lex}}}}
\def\coordle{\mathrel{\preceq_{\text{c}}}}
\def\coord<{\mathrel{\prec_{\text{c}}}}
\newcommand{\etree}{\texttt{nil}}

\begin{problem}
Define \emph{lexicographic order}, $\prec$ on $\naturals^2$ by the rule:
\[
(a_2,b_2) \prec (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 $\prec$-decreasing sequence
\begin{equation}\label{dc}
(a_1,b_1) \succ (a_2,b_2) \succ \cdots \succ (a_n,b_n) \succ \cdots
\end{equation}

\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) \succ (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}


\instatements{\newpage}
\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 be $\coordle$ than the
current move, where $\coordle$ is the coordinatewise partial order.  (An
equivalent way to say this is that if $(x,y)$ is the current move and
$(x',y')$ is any previous move, then either $x<x'$ or $y<y'$.)  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.
}

\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{value}, $\nu$, of a game position to be
$(x_m+y_m,k)$ where $k$ is the number of possible moves left in the
bounded rectangle, and use this derived variable to conclude that the game
must terminate.

\solution{From (i.) and (ii.), we have that $\nu$ is a strictly decreasing
variable under lexicographic order on $\naturals^2$.  Since lexicographic
order is well-founded, 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.}


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

\iffalse

\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}
Recursive ordered trees (ROT's) are defined recursively as follows:
\begin{enumerate}

\item The empty tree, $\etree$, with no nodes, is a ROT.

\item If $T_0,T_1,\dots$ are ROT's with no nodes in common, then a tree
with a new root node is a ROT when for all $n \in \naturals$,
\begin{itemize}

\item if $T_n = \etree$, then no edge labelled $n$ leaves the root, and

\item if $T_n \neq \etree$, then a unique edge labelled $n$ goes from the
new root to the root of $T_n$.
\end{itemize}
\end{enumerate}

Let $T$ be any ROT.  Consider a function $F_T$ satisfying the following
conditions:
\begin{align}
F_{\etree}(n) & = n+1,\label{fe}\\
F_T(0) & =  0,  &  \text{for } T \neq \etree\label{f0}\\
F_T(n+1) & = 1+ F_{T_{F_T(n)}}(F_T(n)).\label{ft}
\end{align}

\bparts

\ppart\label{S} Let $S$ be the ROT with one node (so $S_n \eqdef \etree$
for all $n$).  Prove that $F_S(n) = 2n$.

\solution{By induction on $n$.

\textbf{Base case} $n=0$: $F_S(0) = 0 = 2 \cdot 0$ by~(\ref{f0}).

\textbf{Inductive step:} Assuming by induction that $F_S(n) = 2n$, we need
only show that $F_S(n+1)=2(n+1)$.  But this follows because:
\begin{align*}
F_S(n+1) & = 1+ F_{S_{F_S(n)}}(F_S(n)) & \text{(by~(\ref{ft}))}\\
         & = 1+ F_{S_2n}(2n)  & \text{(by induction hypothesis)}\\
         & = 1+ F_{\etree}(2n)  & \text{(by def.\ of $S$)}\\
         & = 1 + (1+ 2n)   & \text{(by~(\ref{fe}))}\\
         & = 2(n+1).
\end{align*}
}


\ppart Let $R$ be the ROT such that $R_n = S$ for all $n$.
Prove that $F_R(n) = 2^n-1$.

\solution{By induction on $n$.

\textbf{Base case} $n=0$: $F_R(0) = 0 = 2^{0}-1$ by~(\ref{f0}).

\textbf{Inductive step:} Assuming by induction that $F_R(n) = 2^n-1$, we need
only show that $F_R(n+1)=2^{n+1}-1$.  But this follows because:
\begin{align*}
F_R(n+1) & = 1+ F_{R_{F_R(n)}}(F_R(n)) & \text{(by~(\ref{ft}))}\\
         & = 1+ F_{S_{2^n-1}}(2^n-1)  & \text{(by induction hypothesis)}\\
         & = 1+ F_{S}(2^n-1)  & \text{(by def.\ of $R$)}\\
         & = 1 + 2(2^n-1)   & \text{(by part~(\ref{S}))}\\
         & = 1+ (2^{n+1}-2) = 2^{n+1}-1.
\end{align*}
}

\ppart Use the fact that the strict subtree relation, $\prec_\text{SS}$,
defines a well-founded partial order on ROT's, to prove that the
equations~(\ref{fe}),~(\ref{f0}),~(\ref{ft}) uniquely define $F_T$ for any
ROT, $T$.  That is, if $G_T$ is a function such that
equations~(\ref{fe}),~(\ref{f0}),~(\ref{ft}) hold when ``$F$'' is replaced
by ``$G$,'' then $F_T = G_T$.

\solution{
Suppose to the contrary that $F_R \neq G_R$ for some ROT, $R$.  Then there
is a $\prec_{\text{SS}}$-minimal such tree, $T$.  By LNP, there is a least
$n_0 \in \naturals$ such that
\begin{equation}\label{fg}
F_T(n_0) \neq G_T(n_0).
\end{equation}

Clearly, $T \neq \etree$ because $F_{\etree}(n_0) = n_0+1 = G_{\etree}(n_0)$
by~(\ref{fe}).  Likewise, $n_0 >0$ since $F_T(0) =0= G_T(0)$
by~(\ref{f0}).  So
\begin{align*}
G_T(n_0) & = 1+ G_{T_{G_T(n_0-1)}}(G_T(n_0-1)) & \text{(by~(\ref{ft}))}\\
    &= 1+ G_{T_{F_T(n_0-1)}}(F_T(n_0-1)) & \text{($F_T(n_0-1) =
                F_T(n_0-1)$ by minimality of $n_0$)}\\
   & = 1+ F_{T_{F_T(n_0-1)}}(F_T(n_0-1)) & \text{($F_{T_k} =
               G_{T_k}$ for all $k$ by minimality of $T$)}\\
   & = F_T(n_0) \text{(by~\ref{ft})}.
\end{align*}
This contradicts~(\ref{fg}).  We conclude that $F_T = G_T$, as claimed.
}

\eparts

\end{problem}

\end{document}
