\documentclass[11pt,twoside]{article}
\usepackage{amsmath}
\usepackage{psfig}

\input{/pub/www/classes/6.042/fall99/inputs/macros-course}
\newcommand{\cross}{\times}
\newcommand{\eqdef}{\mathbin{::=}}

\newcommand{\solution}[1]{\smallskip \textbf{Solution:} #1 \textbf{endsoln} \smallskip}

\begin{document}

\tutn{11}{10/21/99}{October 21, 1999}

\section{Strategies for Terminating Games}

In this tutorial we will develop a fundamental theorem about games like
chess, checkers, or tic-tac-toe.  These are games in which two players
alternate moves that depend only on the visible board position or
\emph{state} of the game.  Such games are technically called \emph{two
person games of perfect information} because the players know the complete
state of the gam.  (Most card games are \emph{not} games of perfect
information because neither player can see the other's hand.)

Two person games of perfect information can be represented abstractly by
their "game trees": the root of a game tree corresponds to the start
position of the game.  It has a child for each position after a possible
starting move of the first player.  Each of these children in turn has
children (these are grandchildren of the root) corresponding to the
positions of the game after possible moves by the second player, and so
on.

For example, in the game tree for tic-tac-toe, the root has nine children
corresponding to the nine boxes that the first player could mark with an
"X".  Each of these nodes has eight children corresponding to the eight
remaining boxes which the second player could mark with an "O", and so on.

In general, each node corresponds to a state of the game, and its children
correspond to the states which result from each of the possible moves by
the player whose turn it is.  The leaves of the tree correspond to
situations where no moves are possible---the game is over.  A path from
the root to a leaf describes an individual game or \emph{play} of the
game.  (In English, ``game'' can be used in two senses: we can say that
chess is a game, and we can also play a game of chess.  The first usage
refers to the game tree, and the second usage refers to what we call a
``play.'')

\begin{problems}

\problem
\bparts
\ppart
How many children does the root of a game tree for chess have?  What is
the first level of the tree where two nodes on that level have different
numbers of children?

\solution{20 moves from the root (level 0), namely 16 pawn moves and 4
knight moves.  Same at level 1 for the second player.  But at level 2,
corresponding to first player's second move, there are different numbers
of choices.}

\eparts

In many games like tic-tac-toe or chess, a play may end with a draw, but
it's slightly simpler to develop our game theory if we forbid draws (for
example, we could rule that all draws counts as wins for the second
player).  So we label the leaves of the game tree with \texttt{win} or
\texttt{lose} indicating the outcome for the first player.  (A win for one
player is a loss for the other--- no "everybody wins"-type games at
MIT. {\tt :-)}.)

A \emph{strategy} for a player in a game specifies which move the player
should make in any state in which it is that player's turn to move.  A
\emph{winning} stategy ensures that the player will win no matter what
moves the other player makes.

In tic-tac-toe for example, most elementary school children figure out
strategies for both players that each ensure that the other player can
never get ``tic-tac-toe''.  If we count a play that ends without a
tic-tac-toe as a win for the second player, then the strategy which
prevents the first player from getting ``tic-tac-toe'' is a winning
strategy for the second player.  (Of course the first player can win if
his opponent plays childishly, but not if the second player follows the
winning strategy.)  In this problem we will prove the

\begin{theorem}\label{fund}
\textbf{Fundamental Theorem for two-person games of perfect information}:
For games in which every play eventually ends in win or lose, there is a
winning strategy for one of the players.
\end{theorem}

Although the theorem guarantees a winning strategy, it gives no clue which
player may have it.  For chess or checkers (assuming we agree to some rule
for deciding on a winner in any final position), no one knows which player
has a winning strategy.

\bparts
\ppart Why must every play of chess eventually end?  How about checkers?

\solution{

Chess has a rule that if any position is repeated twice, then the play
ends in a draw (``stalemate'')---which we would count as a win for the
second player.  Since there are only finitely many board positions in
chess, and none can occur more than two times before the play ends, a play
can last at most $2n+1$ moves, where $n$ is the total number of possible
board positions---which is enormously large by the way.  In practice, the
nature of chess causes plays to end in under 100 moves.

I don't know if checkers has a similar rule.  If not, a play could
continue forever by having opposing kings cycle around each other.

}

\eparts

The familiar games mentioned above all have finite game-trees, but not all
games do.  For example, in Problem Set 6, Problem 2, you found a winning
strategy for the ``choose a pair of natural numbers'' game (the problem is
repeated at the end of this handout for reference).  This tree is
infinitely ``wide:'' namely, there are nodes that have an infinite number
of children.  The root is such a node, since the first move can be the
choice of any pair of natural numbers.  The tree is also infinitely
``deep'' because there is no finite bound on how long the game can
continue.

\bparts

\ppart Suppose player 1 chooses the pair (0,1).  Show that there is still
no finite bound on how long the choose-a-pair play might continue.

\solution{
Player 1 can choose $(10^{100},0)$ for example. Then they
choose $(10^{100}-1,0),(10^{100}-2,0), \dots$.}

\eparts

But even though the choose-a-pair tree is so infinite, Problem Set 6
established that every choose-a-pair play terminates.  Abstractly, this
means that although the tree has \emph{longer and longer finite paths} down
from the root, it has \emph{no infinite paths} from the root.

\begin{defin}
A rooted tree is called \emph{finite-path} iff it has no infinite paths
leading away from the root.
\end{defin}

\iffalse
The simplest a finite-path tree whose root has an infinite number of
children and each child of the root is at the top of a finite chain of
descendents one longer than the previous child's.  The first seven
branches of this tree are shown in Figure~\ref{fin-path-tree}.

The two-person games of perfect information in which every play eventually
ends in win or lose are precisely those games whose game trees are
finite-path.  These are the games to which the Fundamental Theorem
applies.

\begin{figure}[htbp]
\centerline{\psfig{figure=fptree.eps,height=3in}}
\caption{\em The first seven branches of a finite-path tree with paths of
every finite length.}
\label{fin-path-tree}
\end{figure}
\fi

Let $\prec$ be the binary relation on rooted trees ``is (isomorphic to)
a \emph{proper} subtree of.''  Formally, $T_1 \prec T_2$ iff there is a
\emph{non-root} vertex $v$ of $T_2$ such that $T_1$ is isomorphic to the
subtree of $T_2$ rooted at $v$.

In the next parts of this problem you will prove:

\begin{theorem}\label{wpo}
The relation $\prec$ is a strict partial order on finite-path trees.
That is, $\prec$ is transitive and \emph{asymmetric}: if $T_1,T_2$ are
finite-path tree and $T_1 \prec T_2$, then $\neg[T_2 \prec T_1]$.
Moreover, $\prec$ is a \emph{well-founded partial order}: every nonempty set of
finite-path trees contains a minimal element.
\end{theorem}

\begin{problemparts}

\problempart Assuming this Theorem~\ref{wpo} for the moment, prove the
Fundamental Theorem~\ref{fund}.  \hint Suppose not.  Then the set of
finite-path trees without winning strategies has a minimal element.

\solution{

Let $T$ be a minimal tree without a winning strategy for either player.
Since every child, $C$, of the root of $T$ is strictly smaller than $T$,
that is $C \prec T$, there must be a winning strategy for one of the
players in the game starting at the root of $C$.  But if some $C$ had a
winning strategy for its second player, then player 1 on $T$ has a winning
strategy: choose $C$ on the first move, and then follow the second
player's winning strategy on $C$.  Since there is no such winning strategy
on $T$, it must be that every child $C$ has a winning strategy for the
first player in the game starting at its root.  But that means that the
second player on $T$ has a winning strategy: if the first player on $T$
picks $C$, then follow the winning strategy for the first player on $C$.
This contradicts the hypothesis that $T$ has no winning strategy.

}

\eparts

Complete the proof of the Fundamental Theorem by proving:

\bparts

\ppart
The relation $\prec$ is a strict partial order on finite-path trees.  

\solution{

\begin{proof}
\begin{itemize}
\item
$\prec$ is transitive: Suppose a copy of $T_1$ is a subtree of $T_2$;
then there is path, $P$, from the root of the $T_1$-copy to the root of
$T_2$.  Suppose also that a copy of $T_2$ is a subtree of $T_3$; then
there is path, $Q$, from the root of the $T_2$-copy to the root of $T_3$.
Now the $T_2$-copy has a copy of the $T_1$-copy as a subtree; call this
subtree $T'_1$.  So the path $P$ has a copy, $P'$, from the root of $T'_1$
to the root of the $T_2$-copy.  This means that the path $P'$ followed by
the path $Q$ leads from the root of $T'_1$ to the root of $T_3$.  So
indeed, there is a copy of $T_1$, namely $T'_1$, which is a proper subtree
of $T_3$.

\item
We show that $\prec$ is asymmetric: Suppose (a copy of) $T_1$ is a proper
subtree of $T_2$ and also $T_2$ is a proper subtree of $T_1$.  Then $T_1$
has a copy of itself as a proper subsubtree, as illustrated in Figure 1,
attached.  Therefore there is a path --- which must be of length two or
more --- from the root of $T_1$ to the root of the copy of $T_1$.  This
path extends to a path of length four or more to the root of the copy in
the copy, and then extends to the root of the copy in the copy in the
copy\dots.  In this way we can find an infinite path from the root of
$T_1$, contradicting the assumption that $T_1$ is finite-path.
\end{itemize}
\end{proof}
}

\ppart  The relation $\prec$ is well-founded on finite-path trees.

\solution{ Suppose not.  Then, as shown in Handout 18 on well-founded
posets, there must be an infinite $\prec$-decreasing sequence of distinct
elements.  That is, an infinite sequence $T_1 \succ T_2 \succ T_3 \succ
\dots$ of distinct finite-path trees.  By definition, $T_n \succ T_{n+1}$
means there is a path from the root of $T_n$ to a vertex which is the root
of an isomorphic copy of $T_{n+1}$.  It's convenient to assume that
$T_{n+1}$ itself --- rather than an isomorphic copy --- is the subtree of
$T_n$.  As illustrated in Figure 2.  This assumption is justified because
we could always replace $T_{n+1}$ in the sequence above with the actual
subtree of $T_n$ isomorphic to it.

Now $T_n \succ T_{n+1}$ implies there is a path $P_n$ (necessarily of
length one or more) from the root of $T_n$ to the root of $T_{n+1}$.  But
then $P_1$ followed by $P_2$ followed by $P_3$ \dots is an infinite path
from the root of $T_1$, contradicting the hypothesis that $T_1$ is
finite-path.  Hence there cannot be such an infinite decreasing sequence
of finite-path trees, and this implies that the set of finite-path trees
partially ordered by $\prec$ is a well-founded poset.
}

\eparts


\iffalse
\problem In this problem we'll generalize the choose-a-pair game to
``choose-a-tuple''.  Here are the rules:

Player 1 chooses any integer $n\geq 1$.  Then player 2 chooses any
$n$-tuple of natural numbers.  After that, the players alternate moves,
choosing at each move any $n$-tuple of natural numbers which is NOT
coordinatewise $\geq$ any previously chosen $n$-tuple.  The game ends when
some player cannot move.

For example, player 1 might begin by choosing $n=3$.  Then player 2 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 1 with only the move (0,0,0), and the game ends
since no more moves are possible.

It turns out that every one of these games must end at some point; no game
can go on forever!  You proved this for the $n=2$ case on Problem Set 6 by
applying an ingenious, \emph{ad hoc}, well-ordering to the states of the
game.  Rather than try to generalize that bit of ingenuity (which can get
messy), we'll help you to prove this remarkable fact by developing
properties of a special class of well-founded posets.

\begin{defin}
A poset $(P,\prec)$ is \emph{well-quasi-ordered} iff, for every nonempty
subset $S \subseteq P$ has at least one, but at most a finite number of,
minimal elements.
\end{defin}

\bparts

\ppart Prove:
\begin{lemma}\label{coord-wqo}
Suppose  $(P, \leq_P)$ and $(Q, \leq_Q)$ are well-quasi-ordered posets.
Then so is $P \cross Q$ under the coordinatewise partial order.
\end{lemma}

\solution{

Suppose $\emptyset \neq S \subseteq P \cross Q$.  We first prove $S$ has
at least one minimal element.  This was proved in S99, Handout 18 as
follows:

\begin{proof}
Then $\set{p \in P \mid (p,q) \in S \mbox{ for some } q \in Q}$ is a
nonempty subset of $P$, and so has a $\leq_P$-minimal element $m_P$.  Now
$\set{q \in Q \mid (m_P,q) \in S}$ is a nonempty subset of $Q$ and so has
a $\leq_Q$-minimal element $m_Q$.  It follows that $(m_P,m_Q)$ is a
coordinatewise minimal element of $S$.
\end{proof}

Now suppose $S$ had an infinite set $F \subseteq S$ of minimal elements.  
Then $\set{p \in P \mid (p,q) \in F \mbox{ for some } q \in Q}$ is
a nonempty subset of $P$, and so has only finitely many minimal elements
of $P$.  TO BE COMPLETED
}

\ppart Now prove that any choose-a-tuple game must end.

\solution{
\begin{proof}
Just show by induction on $n\geq 1$ that $\naturals^n$ under
coordinatewise order is well-quasi-ordered.  The base case $n=1$ is
immediate, and Lemma~\ref{coord-wqo} handles the induction case.
\end{proof}
}

\eparts
\fi

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\problem  %S98 Q1

Start with 102 coins on a table, 98 showing ``heads'' and 4 showing
``tails.''  There are two ways to change the coins:
\begin{enumerate}
\item[(i)] flip over any ten coins, or

\item[(ii)] let $n$ be the number of coins on the table showing heads.  Place
$n+1$ additional coins on the table, with all the new coins initially
showing tails.
\end{enumerate}
For example, you might begin by flipping nine heads and one tail,
yielding 90 heads and 12 tails, then add 91 tails, yielding 90 heads and
103 tails.

\bparts
\ppart
Model this situation as a state machine, carefully defining the set of
states, the start state and the possible state transitions.

\solution{
This can be modeled by a state machine $M=\{Q,Q_0,\delta\}$, where:\\

\begin{itemize}
\item $Q=\naturals\times\naturals$, the first integer is the number of
heads and the second integer is the number of tails;

\item  $Q_0=\{(98,4)\}$

\item  $\delta$ is given by the rule that the next state of $(h,t)$ can be
any state of the form:\\
\[\begin{array}{l}
(h-a+(10-a),t+a-(10-a)) \mbox{ where }0\leq a\leq 10,\ a\leq h,\ 10-a\leq t,\\
\mbox{or }(h,t+h+1).\\
\end{array}\]
\end{itemize}

\vskip0.5in
{\bf Comment:} Most students forgot to specify the range of $a$ precisely
for the first transition.
}

\ppart Explain how to reach a state with exactly one tail showing.

\solution{
\begin{enumerate}

\item Do operation 2 three times, yielding $(98, 4+3\cdot99)= (98,301)$.

\item Repeat 30 times: Do operation 1 to flip 10 tails into heads. This
will result in the state $(398,1)$, which is the desired state.
\end{enumerate}
}

\ppart
Define the following derived variables of a state $q$:
\begin{eqnarray*}
 C(q) & \eqdef & \mbox{ the number of coins on the table},\\
 H(q) & \eqdef & \mbox{ the number of heads},\\
 T(q) & \eqdef & \mbox{ the number of tails},\\
 C_2(q) & \eqdef & \mbox{remainder}(C(q)/ 2),\\
 H_2(q) & \eqdef & \mbox{remainder}(H(q)/ 2),\\
 T_2(q) & \eqdef & \mbox{remainder}(T(q)/ 2).
\end{eqnarray*}

Which of these variables is
\begin{enumerate}

\item increasing \solution{NONE}
\item\label{ndec} nondecreasing \solution{$C(q)$, $H_2(q)$}
\item decreasing \solution{NONE}
\item constant \solution{$H_2(q)$.

{\bf Comment:} A lot of students failed to notice that a constant variable
is also a nondecreasing variable, and did not put $H_2(q)$ in part~\ref{ndec}.
}
\end{enumerate}


\ppart Prove that it is not possible to reach a state in which there is
exactly one head showing.

\solution{

We claimed above that $H_2(q)$ is an invariant value, that is, it does not
change under state tramsitions.  To prove this, let $(h,t)$ be a state
with $h$ even.  For the next state, we have two cases to consider:
\begin{enumerate}
\item The first operation is executed:
$(h,t)\rightarrow(h-2a+10,t+2a-10)$.  Since $-2a+10$ is even, $H_2((h,t))=
H_2(h-2a+10, t+2a-10)$.

\item The second operation is executed: $(h,t)\rightarrow(h,t+h+1)$. The
number of heads does not change in this case, so $H_2$ does not change.
\end{enumerate}
Since the initial number of heads, 98, is even, that is, $H_2((98,4))=0$,
the Invariant Method now implies that the number of heads in a reachable
state is always even.  But since one is odd, it is not possible to reach a
state in which there is exactly one head showing.

}

\eparts

\iffalse
\problem  Four people are interested in participating in
the VI-A program where each person ranks his top choices of companies
and the companies rank the students as well.  The people Albert, Ben,
Chris, and Doug are interested in companies AT\&T, Bellcore, Compaq,
and Draper Labs.  Below are the students' rankings of the companies
and the companies' rankings of the students.

\begin{center}
\begin{tabular}{c|c} 
Student & Companies \\ \hline
Albert:  & Compaq, Bellcore, AT\&T, Draper \\
Ben:     & AT\&T, Bellcore, Draper, Compaq \\
Chris:   & Compaq, Draper, AT\&T, Bellcore \\
Doug:    & Draper, AT\&T, Bellcore, Compaq 
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{c|c}
Company & Students \\ \hline
AT\&T:    & Doug, Albert, Chris, Ben \\
Bellcore: & Chris, Ben, Albert, Doug \\
Compaq:   & Doug, Chris, Albert, Ben \\
Draper:   & Ben, Doug, Chris, Albert
\end{tabular}
\end{center}

\begin{problemparts}
\problempart What is a student-optimal stable marriage set for
this problem?

\solution 

You were guaranteed to get a student-optimal stable marriage set if
you ran the stable marriage algorithm given in lecture, where Students
are Men and Companies are Women.  The result is the following assignment:

\begin{center}
\begin{tabular}{c|c|c} 
Student & Companies & Rank in the original list \\ \hline
Albert:  & Bellcore & 2\\
Ben:     & AT\&T & 1\\
Chris:   & Compaq & 1\\
Doug:    & Draper &1
\end{tabular}
\end{center}

\problempart What is a company-optimal stable marriage set for
this problem?

\solution

Similarly, you were guaranteed to get a company-optimal stable
marriage set if you ran the stable marriage algorithm given in
lecture, where Students are Women and Companies are Men.  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: & Ben & 2\\
Compaq:   & Chris & 2\\
Draper:   & Doug & 2
\end{tabular}
\end{center}




\problempart Are there any other stable marriage sets possible?

\solution
We noted in lecture that the Gale-Shapley dating protocol yields a
(necessarily unique) man-optimal stable marriage assignment, and moreover
this assignment is also the unique women-pessimal one.  Therefore, from
parts (a) and (b) we know that in both student-optimal and
student-pessimal stable marriage sets, Chris is married to Compaq, and
Doug to Draper Labs.  So Chris can never do better or worse than Compaq in
any stable marriage set, viz., he is married to Compaq in all stable
marriage sets; likewise for Doug and Draper.  Hence the possibilities for
Albert and Ben are only AT\&T and Bellcore.  Since both these
possibilities are given in the two solutions above, there are no other
stable marriage sets possible.


\end{problemparts}
\fi

\iffalse

\newpage
% S99 Q1

\problem We apply the following procedure to a digraph $G=(V,E)$:
pick two vertices $v_1 \neq v_2$ such that (1) there is an edge in $E$
from $v_1$ to $v_2$ and (2) there is also a path from $v_1$ to $v_2$ which
does \emph{not} include this edge, and then delete the edge $(v_1,v_2)$.
Keep repeating this deletion process until it is no longer possible to
delete any edge.

This procedure can be modelled as a state machine whose states are all the
subgraphs of $G$, that is, all the digraphs with vertices $V' \subseteq V$
and edges $E' \subseteq E$.  $G$ is the only start state, and the final
states are the subgraphs in which no deletions are possible.

\bparts
\ppart  Let $G$ be the digraph with $V=\set{1,2,3,4}$ and edges
\[
\set{(1,2),(2,1),(2,3),(3,2),(3,1),(2,4)}.
\]
List the possible final states that are reachable from the start state: 

\solution{2 states --- a cycle 1231 or a double loop 21232,
with 2 connected to 4 in each case:
\[
\set{(1,2),(2,3),(3,1),(2,4)},
\]
and
\[
\set{(1,2),(2,1),(2,3),(3,2),(2,4)}.
\]}


\ppart In addition to numerical derived variables, we introduce
some set-valued derived variables below.  For the set-valued derived
variables, values will be partially ordered under containment (that is,
under $\subseteq$).  So such a variable is \emph{decreasing} when its value
after a transition is strictly contained in its value before the
transition.  This also applies to relation-valued variables, since a
relation can be treated as the set of tuples of its related elements.

For each of the variables below, indicate the strongest
property which it satisfies from the following list:
\begin{center}
\begin{tabular}{ccccc}
invariant & increasing & decreasing & nonincreasing & nondecreasing
\end{tabular}
\end{center}
The derived variables are:
\begin{enumerate}

\item[i)] the set of vertices,

\solution{invariant}

\item[ii)] the set of edges,

\solution{decreasing}

\iffalse
\item minimum number transitions to reach a final state, \brule{1in}

\solution{nonincreasng? fluctuates?}
\fi

\item[iii)] the connectedness relation, $\succeq$\\
(Remember for vertices $u,v$:\
\[
u \succeq v \mbox{ iff } [u=v \mbox{ or there is a path from $u$ to $v$}],
\]

\solution{invariant}

\item[iv)] the set of final states reachable from the current state,

\solution{nonincreasing; part (a) shows that it is not invariant.}
\iffalse

\item[v)] the number of simple cycles. \brule{1.5in}
\fi

\item[v)] the minimum length of a path in the graph.

\solution{invariant.  This was a trick question, and it tricked too many
people, indicating not that they were foolish, but that the question was
not a good one.

\medskip
The reason for invariance is that the minimum length of a path is one, as
long as the graph has at least one edge, since an edge is a length one
path.  Also, a graph with at least one edge will never have all its edges
deleted, so the minimum length is invariant in this case.  If the graph
has no edges, then the minimum length is either undefined or zero as a
matter of convention; either way it's invariant.  Of course this is a
silly variable to consider, and that may have encouraged people to look
for other meanings.

\medskip
A less silly derived variable of this kind would be \emph{Max} defined to
be the \emph{maximum} length of a path in the graph --- when there is a
maximum length.  Define \emph{Max} to be -1 when there is no bound on the
length of paths.  Now \emph{Max} is an invariant, and it is genuinely
interesting: \emph{Max} $= -1$ precisely when the graph has a cycle, and
when the graph is a DAG, we know its value is the minimum length of
schedule when edges are interpreted as scheduling precedence constraints.

\medskip
Some people chose \emph{nondecreasing}, perhaps because they
misinterpreted the problem as asking about the minimum length path between
\emph{any given pair of vertices} rather than the minimum length among
\emph{all} pairs.  Indeed, for any given pair which are connected by some
path, the length of the minimum length path between them will never
decrease as a result of deleting edges, and it can increase.}

\end{enumerate}

\ppart Prove that the procedure terminates and that the final
digraph has the same connectedness relation as $G$.

\solution{Since the edge set is decreasing so is the number of edges.
Since it must be a natural number, by the Well-ordering Principle it
cannot decrease forever, and the procedure terminates when it can no
longer be decreased.  The final graph has the same connectedness relation
as $G$ because the relation is an invariant.  (Many people included a
proof of invariance; we did not require this and allowed invariance to be
taken as known from part (b)).}

\ppart Does it also follow from the indicated properties of the
derived variables that the final graph has the minimum number of
edges among all graphs with the same connectedness relation as $G$?
Briefly explain.

\solution{No!  Having the minimum number of edges does not follow because
it isn't true, eg, from part (a), one final state has five edges and the
other has the same connectedness with four edges,

\medskip
Another example is the one vertex graph with a self-loop; anyone picky
enough to spot this degenerate case should get full credit.}


\eparts
\fi

\end{problems}


\newpage
\section{Appendix: PSet6, Prob 2}

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 ten possible bounded moves:
$\{(1,2),(2,1),(1,1),(0,3),(0,2),(0,1),(0,0),(1,0),\\(2,0),(3,0)\}$.
There is also an infinite number of possible unbounded moves at this
point, namely, any move with one coordinate equal to $0$ and the other
larger than $3$.

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')\]

Prove that any nonempty subset of $\naturals^3$ has a least element under
the above ordering.

Prove that under the ordering of $\naturals^3$ defined above, the
measure $M(S)=(X(S),Y(S),B(S))$ decreases at every move in a game.
Conclude that the game always terminates, regardless of the players'
strategy.

\end{document}

