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

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query
\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

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


\begin{document} 
\inclassproblems{5, Fri}                    % !! start the paper

%S98, and (F99?) H45-sol6 

\begin{problem}
%\textbf{Terminating games}

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 the current move must be $\coord<$ or
incomparable to all the previous moves.  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 $(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}
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 Is there any strategy 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 Prove that the game must always terminate, even if the players
conspire to choose strategies that try to keep the game going
indefinitely.

\solution{
This is a tricky problem without some hints.

\hint At any point in the game, let $x_m$ be the minimum of the values of
the $x$ coordinates of any of the previous moves, and likewise, $y_m$ be
the minimum of the values of the $y$ coordinates of any of the previous
moves.  Then $x_m+y_m$ is a \emph{weakly} decreasing natural-number valued
variable.

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

\hint Suppose $a$ is the least number such that a move $(x_m,a)$ has been
made, and likewise $b$ is least such that $(b,y_m)$ has been made.  Then
the only possible moves that do not decrease $x_m+y_m$ must occur in the
rectangle with corners at $(x_m,a)$ and $(b,y_m)$.

\begin{proof}
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$.
\end{proof}

\hint Define the size of a game position to be $(x_m+y_m,k)$ where $k$ is
the number of possible moves left in the rectangle.

\begin{proof}
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{proof}}

\iffalse

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

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

\eparts
\end{problem}

\textbf{NOTE October 4, 2002, 6PM:} We didn't get to either of the
following two problems.

\begin{problem} % F01, tut5

In Week 5 Notes we considered win-lose games, ignoring games which can end
in a draw.  Such games have finite-path game trees in which the leaves are
labelled with \emph{win}, \emph{lose}, or \emph{draw}, indicating the
outcome for the first player.

While a winning stategy for a player ensures the player will win no matter
what moves the other player makes, there is now the possibility of a
\emph{non-losing} stategy which ensures that the player will \emph{win or
draw} no matter what moves the other player makes.  (A winning strategy
counts as a kind of a non-losing strategy.)

For example, in tic-tac-toe there is no winning strategy for either
player, but \emph{both} players have non-losing strategies.  For chess, no
one knows if white or black has a winning strategy.  However, on general
principles, we can be sure that at least one player has a non-losing chess
strategy.

Explain why for any two-person win-lose-draw game with a finite path game
tree, either one player has a winning strategy or \emph{both} players have
non-losing strategies.

\solution{We could prove this the same way we proved the Fundamental
Theorem for win-lose games, using the well-foundedness of finite-path
trees under the ``strict-subtree'' partial order, but it's more elegant to
deduce this as a Corollary of the Fundamental Theorem.

Call the players $C$ and $D$, and suppose neither one has a
winning strategy for the game, $T$.  We want to show that then \emph{both}
players have non-losing strategies for $T$.

The proof is based on the simple observation that in a game with no draws,
a non-losing strategy must be a winning strategy.

To prove that $C$ has a non-losing strategy for the game, $T$, let's
consider another game, $T_C$, identical to $T$ except that draws are
considered wins for player $C$.  Since there are no draws in $T_C$, we
conclude that either $C$ or $D$ has a winning strategy for $T_C$.  But a
winning strategy for $D$ in the $T_C$ game would also be a winning
strategy for $D$ in the original game, $T$, because wins for $D$ are the
same in both games.  But we assumed that $D$ has no winning strategy for
$T$, so it doesn't have one for $T_C$.

That means that $C$ must have the winning strategy for $T_C$.  But a
winning strategy for $C$ in $T_C$ would also be a non-losing strategy for
$C$ in the original game, $T$, because wins for $C$ in $T_C$ are always
wins for $C$ or draws in $T$.  So we conclude that $C$ has a non-losing
strategy for $T$.

Notice that we haven't assumed that $C$ is the first or second
player, so the preceding argument applies equally well to show that $D$
also has a non-losing strategy for $T$, as required.
}
\end{problem}


\begin{problem}
Prove part~\ref{Lwf}.\ of Lemma~\ref{lex-coord-lem} below.
\end{problem}

\solution{From Week 5 Notes, Lemma 8.4:

\begin{proof}
Suppose $\emptyset \neq S \subseteq P_1 \cross P_2$.  Then the set
\[
S_1 \eqdef\ \set{p_1 \in P_1 \suchthat (p_1,p_2) \in S \mbox{ for some }
p_2 \in P_2}
\]
is a nonempty subset of $P_1$, and so has a $\preceq_1$-minimal element,
$m_1$.  This means the set
\[
S_{12} \eqdef\ \set{p_2 \in P_2 \mid (m_1,p_2) \in S}
\]
is a nonempty subset of $P_2$ and so has a $\preceq_2$-minimal element,
$m_2$.  We claim that $(m_1,m_2)$ is a minimal element of $S$ under
\emph{both} the coordinatewise and the lexicographic partial orders on
$P_1 \cross P_2$.

To check this, we consider any element $(n_1,n_2) \in S$ such that
$(n_1,n_2) \preceq (m_1,m_2)$ and prove that $(n_1,n_2) = (m_1,m_2)$,
where $\preceq$ may be either coordinatewise or lexicographic order.

Now we know that
\[
n_1 \preceq_1 m_1
\]
by definition of $\preceq$.  Also $n_1 \in
S_1$, so
\[
m_1 \preceq_1 n_1
\]
by definition of $m_1$.  Hence,
\[
n_1 = m_1.
\]
This means that $n_2 \in S_{12}$, so
\[
m_2 \preceq_2 n_2
\]
by definition of $m_2$.  But since $n_1=m_1$, we have by definition of
$\preceq$, that
\[
n_2 \preceq_2 m_2,
\]
proving that
\[
n_2=m_2,
\]
as claimed.
\end{proof}
}

\newpage
\appendix

\section{From Week 5 Notes}

\begin{definition}\label{wfpo}
A poset $(P,\preceq)$ is \emph{well-founded} iff every nonempty subset $S
\subseteq P$ has a \emph{minimal element}.
\end{definition}

\begin{lemma}
\label{d-chain}
A poset is well-founded iff it has no infinite decreasing chain.
\end{lemma}

\begin{definition}\label{lex-coord-def }
Let $(P_1, \preceq_1)$ and $(P_2, \preceq_2)$ be partial
orders.  The \emph{lexicographic partial order}, $\lexle$, on $P_1
\cross P_2$ is defined by the condition that
\begin{equation}\label{lexc2}
(p_1,p_2) \lexle (q_1,q_2)  \text{  iff  }  [p_1 \prec_1 q_1\text{ or
}(p_1=q_1 \land p_2 \preceq_2 q_2)].
\end{equation}
The \emph{coordinatewise partial order}, $\coordle$, on $P_1
\cross P_2$ is defined by the condition that
\begin{equation}\label{coord2}
(p_1,p_2) \coordle (q_1,q_2) \text{ iff } [p_1 \preceq_1 q_1 \land p_2
\preceq_2 q_2].
\end{equation}
\end{definition}

\begin{lemma}\label{lex-coord-lem}
Suppose $(P_1, \preceq_1)$ and $(P_2, \preceq_2)$ are posets.  Then
\begin{enumerate}

\item\label{Lpo} so are $(P_1 \cross P_2,\lexle)$ and $(P_1 \cross
P_2,\coordle)$.  Moreover,

\item\label{Lwf} if $(P_1, \preceq_1)$ and $(P_2, \preceq_2)$ are both
well-founded, then so are $(P_1 \cross P_2,\lexle)$ and $(P_1 \cross
P_2,\coordle)$.

\item\label{Lto} if $(P_1, \preceq_1)$ and $(P_2, \preceq_2)$ are both totally
ordered, then so is $(P_1 \cross P_2,\lexle)$.
\end{enumerate}
\end{lemma}

\end{document}
