\documentstyle[12pt,twoside]{article}

\newcommand{\problem}{%
  \paragraph{Problem}}
\newcommand(\solution}{%
  \paragraph{Solution}}

\begin{document}\induction


\begin{problems}

%BEGIN Kavita's problems
% Fall 1998


%**************
%   PSET 3    *
%**************

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

\problem {\bf (10 points)} 
Let $G_n$ be a directed graph with vertices numbered $0, 1,
\ldots, n-1$.  There is a directed edge from vertex $i$ to vertex $j$
if and only if $j \equiv i^2 + i + 1 \pmod{n}$.  (See page 119 of
Rosen for a definition of $\equiv$ and $\pmod{n}$.  As a hint,
however, no number theory is required to solve this problem.)

\begin{problemparts}

\problempart Draw the directed graphs $G_1$, $G_2$, and $G_3$.

\begin{figure}[h!]
\centerline{\resizebox{4.0in}{!}{\includegraphics{figs/f98ps3-digraph.eps}}}
\end{figure}

\problempart Prove that if $n \geq 1$, then $G_n$ is not a directed
acyclic graph.

\solution{
\begin{proof}
Consider the following sequence of vertices in graph $G_n$.

\begin{eqnarray*}
v_1 & = & 0 \\
v_2 & = & v_1^2 + v_1 + 1 \pmod{n} \\
v_3 & = & v_2^2 + v_2 + 1 \pmod{n} \\
\ldots & & \ldots \\
v_{n+1} & = & v_n^2 + v_n + 1 \pmod{n}
\end{eqnarray*}

Note that there is a directed edge from $v_i$ to $v_{i+1}$ for all $1
\leq i \leq n$.  Not all of the vertices $v_1, \ldots, v_{n+1}$ can
be distinct, since the graph contains only $n$ vertices.  Suppose
$v_j$ is the first vertex in the sequence to appear a second time, and
$v_k$ was the initial appearance of that vertex.  Than the sequence of
vertices $v_k, v_{k+1}, \ldots, v_{j-1}$ forms a directed cycle.
Therefore, $G_n$ is not a directed acyclic graph.
\end{proof}
}

\end{problemparts}


\problem {\bf (20 points)} 
A {\em linear extension} of a poset is a
total order consistent with the partial order.  That is, if $x > y$ in
the partial order, then $x > y$ in the total order also.  For example,
in the poset defined by the Hasse diagram below, the following
relationships hold: $a > b$, $a > c$, $a > d$, $a > e$, $b > c$, and
$b > d$.

\begin{figure}[h]
\centerline{\resizebox{!}{1.5in}{\includegraphics{figs/f98ps3-partial.eps}}}
\end{figure}

This poset has eight linear extensions, which are listed in the table below.  To
clarify the notation, the upper-left entry represents the total order
where $a$ is the largest element, $b$ the second largest, and so
forth.  Note that all of the relationships that hold in the poset also
hold for all the total orders listed below.

\[
\begin{array}{ccc}
a > b > c > d > e	& \quad \quad &		a > b > d > c > e \\
a > b > c > e > d	&	&		a > b > d > e > c \\
a > b > e > c > d	&	&		a > b > e > d > c \\
a > e > b > c > d	&	&		a > e > b > d > c
\end{array}
\]

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

\problem {\bf (15 points)} 
An {\em automorphism} of a graph is a relabeling of the
vertices that preserves adjacency.  For example, the graph on the left
side of the figure below has the automorphism $a \rightarrow b, b
\rightarrow a, c \rightarrow c, d \rightarrow d$.  (Here the
notation $x \rightarrow y$ means that the vertex labeled $x$ is
relabeled $y$.)  The relabeled graph is shown on the right side of the
figure.  This relabeling is an automorphism because adjacency is
preserved; that is, in the relabeled graph, just as in the original,
$a$ is adjacent to $b$ and $c$; $b$ is adjacent to $a$ and $c$; $c$ is
adjacent to $a$, $b$, and $d$; and $d$ is adjacent to $c$.  Every
graph has a {\em trivial automorphism} that assigns each node its
original label.

\begin{figure}[h!]
\centerline{\resizebox{!}{1.5in}{\includegraphics{figs/f98ps3-auto.eps}}}
\end{figure}

\begin{problemparts}

\problempart List all non-trivial automorphisms of the graph below using the
$x \rightarrow y$ notation as in the example.

\begin{figure}[h!]
\centerline{\resizebox{!}{1.5in}{\includegraphics{figs/f98ps3-findauto.eps}}}
\end{figure}

\solution{
\[
\begin{array}{c}
a \rightarrow e, b \rightarrow f, c \rightarrow c, d \rightarrow d,
e \rightarrow a, f \rightarrow b, g \rightarrow g, h \rightarrow h \\

a \rightarrow e, b \rightarrow f, c \rightarrow c, d \rightarrow d,
e \rightarrow a, f \rightarrow b, g \rightarrow h, h \rightarrow g \\

a \rightarrow a, b \rightarrow b, c \rightarrow c, d \rightarrow d,
e \rightarrow e, f \rightarrow f, g \rightarrow h, h \rightarrow g
\end{array}
\]
}

\problempart Draw a graph with at least 2 nodes that has only the trivial
automorphism.

\solution{
\begin{figure}[h!]
\centerline{\resizebox{!}{1.0in}{\includegraphics{figs/f98ps3-noauto.eps}}}
\end{figure}
}

\end{problemparts}

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

\problem {\bf (15 points)} 
An $n$-node graph is said to be {\em tangled} if there is an edge
leaving every set of $\lceil\frac{n}{3}\rceil$ or fewer vertices.  As
a special case, the graph consisting of a single node is considered
tangled.  (Recall that the notation $\lceil x \rceil$ refers to the
smallest integer greater than or equal to $x$.)

\begin{problemparts}

\problempart Find the error in the proof of the following claim.

\bigskip

{\bf Claim.} Every non-empty, tangled graph is connected.

\bigskip

\begin{proof}
The proof is by strong induction on the number of vertices in the
graph.  Let $P(n)$ be the propostion that if an $n$-node graph is
tangled, then it is connected.  In the base case, $P(1)$ is true
because the graph consisting of a single node is defined to be tangled
and is trivially connected.

In the inductive step, for $n \geq 1$ assume $P(1), \ldots, P(n)$ to
prove $P(n+1)$.  That is, we want to prove that if an $(n+1)$-node
graph is tangled, then it is connected.  Let $G$ be a tangled,
$(n+1)$-node graph.  Arbitrarily partition $G$ into two pieces so that
the first piece contains exactly $\lceil\frac{n}{3}\rceil$ vertices,
and the second piece contains all remaining vertices.  Note that since
$n \geq 1$, the graph $G$ has a least two vertices, and so both pieces
contain at least one vertex.  By induction, each of these two pieces
is connected.  Since the graph $G$ is tangled, there is an edge
leaving the first piece, joining it to the second piece.  Therefore,
the entire graph is connected.  This shows that $P(1), \ldots, P(n)$
imply $P(n+1)$, and the claim is proved by strong induction.
\end{proof}

\solution{
The error is in the statement, ``By induction, each of these two
pieces is connected.''  This is not what the induction hypothesis
says; the induction hypothesis states that {\em if a graph is
tangled}, then it is connected.

In abstract terms, we are proving an induction hypothesis of the form
``if (this), then (that)''.  However, we erroneously use the induction
hypothesis as if it were simply of the form ``(that)'.
}

\problempart Draw a tangled graph that is not connected.

\solution{
\begin{figure}[h!]
\centerline{\resizebox{!}{1in}{\includegraphics{figs/f98ps3-tangled-cx.eps}}}
\end{figure}
}

\problempart An $n$-node graph is said to be {\em mangled} if there is an edge
leaving every set of $\lceil\frac{n}{2}\rceil$ or fewer vertices.
Again, as a special case, the graph consisting of a single node is
considered mangled.  Prove the following claim.

\bigskip

{\bf Claim.} Every non-empty, mangled graph is connected.

\solution{
\begin{proof}
The proof is by contradiction.  Assume for the purpose of
contradiction that these exists an $n$-node graph that is mangled, but
not connected.  Then the graph must have at least two connected
components.  However, there can be at most one connected component
with more than $\lceil\frac{n}{2}\rceil$ vertices, since the graph has
only $n$ vertices in total.  Therefore, there exists a connected
component with $\lceil\frac{n}{2}\rceil$ or fewer vertices.  Since the
graph is mangled, there is an edge leaving this component.  But this
contradicts the definition of a connected component.
\end{proof}
}

\end{problemparts}

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

\problem {\bf (15 points)} 
Let $G$ and $H$ be undirected graphs with no self-loops.  The {\em
product graph} $P = G \times H$ is defined as follows.  The vertex set
of $P$ is the cartesian product of the vertex set of $G$ and the
vertex set of $H$.  Thus, each vertex of $P$ is an ordered pair $(v,
w)$ where $v$ is a vertex of $G$ and $w$ is a vertex of $H$.  The
edges in the product graph $P$ are of two types.  First, for every
edge $(v_1, v_2)$ in $G$ and vertex $w$ in $H$, there is an edge
between $(v_1, w)$ and $(v_2, w)$ in $P$.  Second, for every vertex
$v$ in $G$ and edge $(w_1, w_2)$ in $H$, there is an edge between $(v,
w_1)$ and $(v, w_2)$ in $P$.  Note that these two sets of edges are
disjoint.

\begin{problemparts}

\problempart Draw the product of the two graphs shown below.  
Your diagram must be tidy to receive full credit.  In particular,
label all the vertices, e.g. $(b, 3)$, and use two different colors or
line styles (e.g. dashed and solid) to distinguish the two types of
edge defined above.

\begin{figure}[htbp]
\centerline{\resizebox{!}{1in}{\includegraphics{figs/f98ps3-twographs.eps}}}
\end{figure}

\solution{
\begin{figure}[htbp]
\centerline{\resizebox{!}{1.5in}{\includegraphics{figs/f98ps3-product.eps}}}
\end{figure}
}

\problempart Let $G$ be the graph consisting of two vertices connected
by an edge.  Let $G^n$ be the product of $n$ copies of $G$.  Use
induction to prove that $G^n$ has $2^n$ vertices and $n 2^{n-1}$
edges.  (You may assume without proof that the $\times$ operation is
associative.)

\solution{
\begin{proof}
The proof is by induction on $n$.  Let $P(n)$ be the proposition that
$G^n$ has $2^n$ vertices and $n 2^{n-1}$ edges.  In the base case,
$P(1)$ is true because $G^1$ has $2^1 = 2$ vertices and $1 \cdot
2^{1-1} = 1$ edge.

In the inductive step, for $n \geq 1$ assume that $G^n$ has $2^n$
vertices and $n 2^{n-1}$ edges to prove that $G^{n+1}$ has $2^{n+1}$
vertices and $(n+1) 2^n$ edges.  The remainder of the argument uses
the fact that $G^{n+1} = G^n \times G$.

The vertex set of $G^{n+1}$ is the cartesian product of the vertex set
of $G^n$ and the vertex set of $G$.  There are $2^n$ vertices in $G^n$
by induction, and there are 2 vertices in $G$ by the definition of the
graph.  Therefore, there are $2^n \cdot 2 = 2^{n+1}$ vertices in
$G^{n+1}$.

The edges of $G^n \times G$ are of two types.  First, for each edge
$(v_1, v_2)$ in $G^n$ and vertex $w$ in $G$, there is an edge between
$(v_1, w)$ and $(v_2, w)$ in $G^{n+1}$.  Thus, the number of edges of
the first type is equal to the number of edges in $G^n$ multiplied by
the number of vertices in $G$, which gives $n 2^{n-1} \cdot 2 = n
2^n$.

Second, for each vertex $v$ in $G^n$ and edge $(w_1, w_2)$ in $G$,
there is an edge between $(v, w_1)$ and $(v, w_2)$ in $G^{n+1}$.
Thus, the number of edges of the second type is equal to the number of
vertices in $G^n$ multiplied by the number of edges in $G$, which
gives $2^n \cdot 1= 2^n$.  Since these two sets of edges are disjoint,
the total number of edges in $G^{n+1}$ is equal to $n 2^n + 2^n =
(n+1) 2^n$.

This shows that $P(n)$ implies $P(n+1)$, and the claim is proved by
induction.
\end{proof}
}

\end{problemparts}

%**************
%   PSET 4    *
%**************
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (10 points)}
Suppose that the dating game is played as described in class.  That
is, girls pursue their favorite boys, boys reject all but their top
prospect, and the game ends when each boy has a single candidate
remaining.  Prove or disprove each of the following assertions.

\begin{problemparts}

\problempart There is always some girl who gets her favorite boy.

\solution{The claim is false.  Suppose that there are three girls
named $A$, $B$, and $C$, and there are three boys named 1, 2, and 3.
Assume that the boys and girls have the preferences shown in the table
below.

\[
\begin{array}{l|l}
\text{girls' picks} & \text{boys' picks} \\ \hline
A : 1, 2, 3	&	1 : C, A, B \\
B : 2, 3, 1	&	2 : A, B, C \\
C : 2, 1, 3	&	3 : A, B, C
\end{array}
\]

The next table shows what happens during the dating game.  There is
one row for each boy, and a column for each stage of the game.  Each
entry lists all the girls pursuing a boy at a given stage.  The girl
rejected at each stage is crossed off.

\[
\begin{array}{c|l|l|l|l}
\text{boy}
& \text{stage 1}& \text{stage 2}& \text{stage 3}
& \text{stage 4} \\ \hline
1 & A		& \not\!\!A, C	& C		& C \\
2 & B, \not\!C	& B   		& A, \not\!\!B	& A \\
3 & 		&		&		& B
\end{array}
\]

In this case, every girl gets her second-favorite boy.
}

\problempart For every number of girls and boys, it is possible for
every boy to get stuck with his least favorite girl.

\solution{The claim is true.  If every girl has a different favorite
boy, then the algorithm terminates immediately and the boys'
preferences are irrelevant.  In particular, every boy may be stuck
with his least-favorite girl.}

\end{problemparts}

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

\problem {\bf (5 points)}
There are two girls, Alice and Betty, and two boys, Steve and Tim.
Alice prefers Steve, but the others' preferences are such that every
boy-girl dating arrangement is stable.  What are Betty, Steve, and
Tim's preferences?

\solution{
Steve prefers Betty, Betty prefers Tim, and Tim prefers Alice.

The key fact is that every dating arrangement must be stable.  If
Steve preferred Alice, then they would be a rogue couple if they were
not dating.  Therefore, Steve prefers Betty.  If Betty preferred
Steve, then they would be a rogue couple if they were not dating.
Therefore, Betty prefers Tim.  If Tim preferred Betty, then they would
be a rogue couple if they were not dating.  Therefore, Tim prefers
Alice.}

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

\problem {\bf (10 points)} Prove or disprove the following claim: for
some $n \geq 3$, there exists a set of boys' and girls' preferences
such that every dating arrangement is stable.

\solution{
The claim is false.

\begin{proof} We will use letters to denote girls and numbers to denoted boys.

There must be some girl $A$ rated worst by at most $n-2$ boys.  The
reason is as follows.  Each boy can rate exactly one girl worst.  If
each of the $n$ girls was rated worst by at least $n-1$ boys, then
there would have to be at least $n (n-1)$ boys in all.  But this is
false when $n \geq 3$, because then $n (n-1)$ exceeds $n$, the actual
number of boys.

Suppose that this girl $A$ is paired with the boy, 1, that she rates
worst.  Since at most $n-2$ boys rate girl $A$ worst, there is some
other boy, 2, that rates a different girl, $B$, worst.  Suppose that
boy 2 is paired with girl $B$.

Now girl $A$ and boy $2$ form a rogue couple.  Girl $A$ prefers every
other boy to her date, 1.  Similarly, boy $2$ prefers every other girl
to his date $B$.  Therefore, $A$ and $2$ prefer one another to their
current dates.
\end{proof}
}

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

\problem {\bf (15 points)} There are $n$ girls in a tennis tournament.
The tournament director hates to see anyone unhappy.  Therefore, he
plans to adjust the outcome of the tournament according to the
following rule: if a player loses all her matches, then he will change
all her losses to wins.  Of course, changing the results in this way
might create a new player who lost all her matches.  Therefore, his
plan is to continue applying his rule until there is no player who
lost all her matches.

The tournament is played and the results are reported to the director.
It so happens that the original tournament contains no cycles.  The
director now begins to adjust the results according to his rule.

\begin{problemparts}

\problempart Use a state machine model and the Invariant Theorem to
prove that the tournament director never creates a cycle through
repeated application of his rule.

\solution{
\begin{proof}
The proof uses the Invariant Theorem.  Define a state machine as
follows.  Let the set of states $Q$ be the set of tournaments.  Let
the set of start states $Q_0$ be an arbitrary acyclic tournament.  Let
the transition relation $\delta$ consist of tournament pairs $(T, T')$
where $T'$ is obtained from $T$ by applying the tournament director's
rule one time.

We will prove that the following invariant holds: the tournament is
acyclic.  In the start state, this invariant holds trivially.  For
each transition $T \rightarrow T'$ in $\delta$, assume that the
invariant holds for $T$ to prove that the invariant holds for $T'$.

Suppose that $p$ is the player with all losses in tournament $T$ that
has all wins in tournament $T'$.  There can be no cycle in $T'$ that
does not involve player $p$, since this would imply a cycle in $T$ as
well.  However, there can be no cycle in $T'$ that does involve
player $p$, since she wins all her matches in $T'$.

Thus the invariant is established by the Invariant Theorem.
\end{proof}
}

\problempart Prove that by applying his rule, the director can never
make everyone happy.  That is, no matter how many times he applies his
rule, there is still a player that lost all her matches.

\solution{
\begin{proof}
The preceding proof implies that the director never creates a
tournament with a cycle.  We will prove that if a tournament does not
contain a cycle, then there is player who lost all her matches.
Together these facts imply that the director can never create a
tournament where every player wins at least one match.

What remains is to prove that if a tournament does not contain a
cycle, then there is a player who lost all her matches.  We will
actually prove the contrapositive: if every player won at least one
match, then the tournament contains a cycle.

Form a sequence of players $p_1, p_2, \ldots, p_{n+1}$ as follows.
Let $p_1$ be an arbitrary player.  Let $p_2$ be one of the players
beaten by $p_1$, let $p_3$ be one of the players beaten by $p_2$, and
so forth.  We can form this sequence because every player won at least
one a match by hypothesis.  Since there are only $n$ players, some
player must appear more than once in the sequence $p_1, p_2, \ldots,
p_{n+1}$.  Let $p_j$ be the first player to appear a second time in the
sequence, and let $p_i$ be the first appearance of that player.  Then
the players $p_i, p_{i+1}, \ldots, p_{j-1}$ form a cycle.
\end{proof}
}

\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%END   Kavita's problems

%BEGIN Joe's problems
%END   Joe's problems

%BEGIN Ray's problems


%%%%%%%%%%%%%%  S99 ps3


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

\problem {\bf (10 points)} The adjacency matrix of a graph is given below.

\[
\left[
\begin{array}{cccccc}
0 & 1 & 1 & 1 & 0 & 1 \\
1 & 0 & 0 & 1 & 1 & 1 \\
1 & 0 & 0 & 1 & 1 & 1 \\
1 & 1 & 1 & 0 & 1 & 0 \\
0 & 1 & 1 & 1 & 0 & 1 \\
1 & 1 & 1 & 0 & 1 & 0
\end{array}
\right]
\]

\begin{problemparts}

\problempart Draw the graph defined by this adjacency matrix.  Label
the vertices of your graph $1, 2, \ldots, 6$ so that vertex $i$
correponds to row and column $i$ of the matrix.

\solution{
\bigskip
\centerline{\resizebox{!}{2.0in}{\includegraphics{figs/adjgraph.eps}}}
\bigskip
}

\problempart Determine the chromatic number of this graph, and
give a coloring of the vertices that uses the minimum number of
colors.

\solution{The diagram above shows a 3-coloring.  The chromatic number
cannot be less than 3, because vertices 1, 2, and 4 are all connected
and therefore must receive distinct colors.  Consequently, the
chromatic number of the graph is exactly 3.}

\end{problemparts}

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

\problem {\bf (10 points)} Let $G$ be a graph.  Prove that there is a
path from every vertex of odd degree to some other vertex of odd
degree.

\solution{
\begin{proof}
If graph $G$ has no vertex of odd degree, then the claim is true
vacuously.  Otherwise, let $v$ be a vertex of odd degree.  Consider a
longest path starting at $v$ in which each edge occurs at most once.
Then every edge leaving the final vertex on the path must already be
on the path.  We will show that this final vertex of the path is
another vertex of odd degree.

Since $v$ has odd degree, the path contains at least one edge.
Furthermore, the final vertex of the path cannot be $v$, since the
edges incident to $v$ would then consist of the first and last edge of
the path plus two edges for each time that the path crosses $v$--- an
even total.  Therefore, the edges incident to the final vertex of the
path consist of the final edge of the path plus two edges for each
time that the path crosses the final vertex--- an odd total, as
claimed.
\end{proof}
}

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

\problem {\bf (15 points)} An edge of a connected graph is called a {\em
cut-edge} if removing the edge disconnects the graph.  Prove that an
edge $e$ in a connected graph $G$ is a cut-edge if and only if no
simple cycle contains $e$.

For this problem, use the definition of a ``simple cycle'' given on
page 468 of Rosen (p.463 in ed.3).  (The lecture notes require a
simple cycle to have no repeated vertex, but Rosen requires no
repeated edge.)

\solution{
\begin{proof}
First, we prove that if $e$ is contained in a simple cycle, then $e$
is not a cut-edge.  Since $G$ is connected, there exists a path $P$
between every pair of distinct vertices $u$ and $v$.  We must show
that there still exists a path between $u$ and $v$ after edge $e$ is
removed.  Let $e, e_1, e_2, \ldots, e_n$ be the edges in a simple
cycle containing $e$.  Since the cycle is simple, none of the edges
$e_1, e_2, \ldots, e_n$ are equal to $e$.  Therefore, we can construct
a new path that connects $u$ and $v$, but does not contain edge $e$ by
substituting either $e_1, e_2, \ldots, e_n$ or $e_n, e_{n-1}, \ldots,
e_1$ in place of edge $e$ in the path $P$.  (Which sequence is
substituted for edge $e$ depends on the direction in which the path
$P$ traverses the edge $e$.)  This shows that the graph remains
connected after edge $e$ is removed, and so edge $e$ is not a
cut-edge.

Next, we prove that if $e$ is not a cut-edge, then $e$ is contained in
a simple cycle.  We will make use of Theorem 1 on page 469 of Rosen
(p.464 in ed.3), which states that there is a {\em simple} path
between every pair of distinct vertices in a connected graph.  Since
$e$ is not a cut-edge, the graph obtained by removing edge $e$ is
connected.  So by the theorem, there exists a simple path $P$
connecting the endpoints of edge edge $e$ even after edge $e$ is
removed from the graph.  Adjoining edge $e$ to path $P$ gives a simple
cycle containing edge $e$.
\end{proof}
}

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

\problem {\bf (15 points)} A graph $G$ is {\em self-complementary} if
$G$ and $\bar{G}$ are isomorphic.  The symbol $\bar{G}$, where $G$ is
a graph, is defined in problem 33 on page 456 of Rosen (p.449 in
ed.3).  The term ``isomorphic'' is defined on page 460 of Rosen (p.454
in ed.3).

\begin{problemparts}

\problempart Draw a self-complementary graph with more than one
vertex.

\solution{The simplest solution is given below.  Edges of the graph
are shown with solid lines, and edges of the complement are shown with
dotted lines.

\bigskip
\centerline{\resizebox{!}{1.5in}{\includegraphics{figs/selfcomp.eps}}}
\bigskip
}

\problempart Give a formula for the number of edges in the complete
graph with $n$ vertices.  No proof is required.

\solution{In a complete graph, each of the $n$ vertices is joined by
edges to $n-1$ other vertices.  However, this counts every edge twice,
once for each endpoint.  Therefore, the number of edges in the
complete graph with $n$ vertices is

\[
\frac{n(n-1)}{2}.
\]
}

\problempart Show that if a graph $G$ is self-complementary, then the
number of vertices in $G$ is congruent to either 0 or 1 mod 4.

\solution{Let $m$ be the number of edges in $G$, let $\bar{m}$ be the
number of edges in the complementary graph $\bar{G}$, and let $n$ be
the number of vertices in each of these graphs.  If $G$ is
self-complementary, then $m$ and $\bar{m}$ must be equal.  Futhermore,
every edge in the complete graph on $n$ vertices is contained in
exactly one of the graphs $G$ and $\bar{G}$.  Therefore, $m + \bar{m}
= \frac{n(n-1)}{2}$.  Putting these two facts about $m$ and $\bar{m}$
together, we find that

\[
m = \bar{m} = \frac{n(n-1)}{4}.
\]

Since the number of edges in a graph must be an integer, $n (n-1)$
must be a multiple of 4.  That is, a self-complementary graph must
satisfy

\begin{eqnarray*}
n (n-1) \equiv 0 \pmod{4}.
\end{eqnarray*}

This congruence holds exactly when the number of vertices $n$ is
congruent to 0 or 1 mod 4.
}

\end{problemparts}


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

\problem {\bf (10 points)} Consider the following table of exchange
rates.  A table entry indicates that one unit of row-currency can be
exchanged for the given amount of column-currency.

\bigskip
\centerline{
\begin{tabular}{c|ccccc}
	    & \$ US & pounds & \$ Canada & euros & rubles \\ \hline
\$ US		& 1.00	& 0.61	& 1.49	& 0.89	& 24.50 \\
pounds		& 1.62	& 1.00	& 2.43	& 1.44	& 40.85 \\
\$ Canada 	& 0.66	& 0.42	& 1.00	& 0.59	& 16.50 \\
euros 		& 1.12	& 0.69	& 1.69	& 1.00	& 28.23 \\
rubles		& 0.04	& 0.02	& 0.05	& 0.03	& 1.00
\end{tabular}
}
\bigskip

%  I assume that the real values of the currencies in US dollars are as
%  follows:
%
%    $ US	pounds		$ Canada	euros		rubles
%    1.00	1.63		0.67		1.13		0.04
%
%  I want most transaction to be lose money, but I'll create a path
%  ($ US -> euros -> $ Canada -> pounds -> rubles -> $US) that
%  makes money.  There might be a shorter cycle that makes money
%  overall, though not with every trade.  Furthermore, I've ensured
%  that one can't do ($ US -> somthing -> $ US) and make money.

\begin{problemparts}
\problempart Express the information in this table using some type of
graph.

\solution{We can represent this table using a weighted, directed graph
as shown below.

\bigskip
\centerline{{\bf Picture to be added.}}
%\centerline{\resizebox{!}{2.5in}{\includegraphics{figs/exchange.eps}}}
\bigskip
}

\problempart Suppose that I have 100 US dollars, and I want to
increase my number of dollars through a sequence of currency
exchanges.  Identify the abstract property that your graph must
possess in order for this to be possible and determine whether or not
your graph has this property.

\solution{There must be a direct cycle containing the US vertex such
that the product of the weights around the cycle is greater than 1.
The graph does contain at least one such cycle, which is shown with a
dotted line above.  The product of the weights around this cycle is
$1.0322\ldots$.}

\end{problemparts}

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

\problem {\bf (15 points)} This problem concerns Hamiltonian circuits
in $n$-cubes.  A {\em Hamiltonian circuit} in a graph is a circuit
traversing every vertex in the graph exactly once.  The $n$-cube is
defined on page 448 of Rosen (p.441 in ed.3).  (Rosen also uses the
name $Q_n$ for an $n$-cube.)  However, the following recursive
definition of an $n$-cube is equivalent to the one given in Rosen, but
may simplify your solutions.  A 0-cube is a single vertex.  An
$(n+1)$-cube consists of two $n$-cubes with corresponding vertices
joined by edges.  For example, a cube is two squares with
corresponding corners joined.

\begin{problemparts}
\problempart Draw a 4-cube.

\solution{
\bigskip
\centerline{\resizebox{!}{2.0in}{\includegraphics{figs/fourcube.eps}}}
\bigskip
}

\problempart In your drawing, highlight a Hamiltonian circuit.

\solution{The dotted edges in the diagram above form a Hamiltonian
circuit.}

\problempart Use induction on $n$ to prove that an $n$-cube has a
Hamiltonian circuit for all $n \geq 2$.

\solution{The proof is by induction.  Let $P(n)$ be the proposition
that an $n$-cube has a Hamiltonian circuit.  In the base case, $P(2)$
is true, because a 2-cube is itself a cycle.

In the inductive step, assume that an $n$-cube has a Hamiltonian
circuit to prove that an $(n+1)$-cube has a Hamiltonian circuit.
Regard an $(n+1)$-cube as two $n$-cubes with corresponding vertices
joined.  The first $n$-cube has a Hamiltonian circuit $H$ by
induction, and there is a matching Hamiltonian circuit $H'$ in the
second $n$-cube.

Take an edge $(u, v) \in H$ and the corresponding edge $(u', v') \in
H'$.  We can construct a Hamiltonian circuit in the $(n+1)$-cube by
starting at vertex $u$, traversing the circuit $H$ all through the first
$n$-cube until reaching vertex $v$, crossing the edge $(v, v')$,
traversing the circuit $H'$ all through the second $n$-cube until
reaching vertex $u'$, and then crossing the edge $(u', u)$.
}
\end{problemparts}

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


\problem {\bf (10 points)} The weighted graph below represents a system
of pipes.  The weight on an edge is the {\em capacity} of the
corresponding pipe; that is, the maximum rate at which water can pass
through the pipe in gallons per second.  Suppose that water enters the
system at vertex $S$ and leaves the system at vertex $T$.  The goal of
this problem is to determine the capacity of the system; that is, the
maximum rate at which water can pass through the entire system in
gallons per second.

\bigskip
\centerline{\resizebox{!}{2.0in}{\includegraphics{figs/flowprob.eps}}}
\bigskip

\begin{problemparts}

\problempart Redraw the system of pipes.  For each pipe, indicate a
rate and direction of flow through the pipe so that the rate of flow
through the entire system is as large as possible.  Make sure that the
rate of flow through a pipe does not violate the limit given in the
diagram above.  Also, make sure that rate of flow into each vertex is
equal to the rate of flow out of the vertex (excluding vertices $S$
and $T$).  This establishes a lower bound on the capacity of the
system.

\solution{With the flow rates and directions shown below, the rate of
flow through the entire system is 7 gallons per second.  Therefore,
the capacity of the system is at least 7 gallons per second.

\bigskip
\centerline{\resizebox{!}{2.0in}{\includegraphics{figs/flowsol.eps}}}
\bigskip
}

\problempart Find a set of pipes with minimum total capacity such that
removing those pipes from the system completely disconnects vertex $S$
from vertex $T$.  Mark these pipes on your diagram.  This establishes
an upper bound on the capacity of the system; the rate of flow from
$S$ to $T$ can be no greater than the total capacity of this set of
pipes.

\solution{The edges marked with X's in the diagram have a total
capacity of 7 gallons per second.  Removing these edges disconnects
$S$ from $T$.  Therefore, the capacity of the system is at most 7
gallons per second.}

\end{problemparts}

To receive full credit, your lower bound on the capacity of the system
from part (a) must equal your upper bound from part (b).


%%%%%%%%%%%% S99 ps4


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

\problem {\bf (15 points)} Unfortunately, I was not able to turn in my
problem set for 6.042 and I need to meet my TA to get it in.  We are
both driving through the city and in order for me to turn in the
problem set we must meet at exactly the same place at the same time.
Given the following map,

\bigskip
\centerline{\resizebox{!}{2.0in}{\includegraphics{figs/map1.eps}}}
\bigskip

\begin{problemparts}
\problempart At each time step, both I and my TA simultaneously move to an
adjacent node in the graph.  We would like to organize our routes such
that we meet at the same node at the same time.  Can we do it?

\solution

No.  I cannot meet my TA on this map: There is no even-length path
that connects the two nodes we are placed on.  Note that a solution
exists if and only if there is an even-length path between the nodes
that I and my TA initially occupy (a path could traverse the same
nodes and edges many times).  You can convince yourself that there is
no even-length path in this example by noting that every simple path
connecting the two nodes has odd length, and furthermore, that this
graph has only even-length cycles, and hence no amount of loops attached
to any of the simple paths can create an even-length path.

In part (c) we will argue that there is an even-length path between
every two nodes on the graph if the graph is connected and not
bi-partite.  The graph in this example is connected but it {\em is}
bi-partite, and if we 2-color it (i.e. partition its vertices into
two disjoint sets $V_1$ and $V_2$ s.t. there is no edges within $V_1$
and no edges within $V_2$) then me and my TA both occupy a node of the
same color.

\problempart How about if we used the following map instead?

\bigskip
\centerline{\resizebox{!}{2.0in}{\includegraphics{figs/map2.eps}}}
\bigskip

\solution

Yes.  Now there is an odd-length path between the two nodes.  Note
that this graph is connected but not bipartite.  Note also that, in
contrast to the previous graph, this one has an odd cycle.

\problempart Describe a general criterion for a graph where I would be able
             to meet my TA at some vertex regardless of our initial positions.

\solution

Such graph must have an even-length path between every two nodes.  A graph
with two or more vertices has this property if and only if it is
connected and not bipartite.  Here is a proof:

\noindent
($\Rightarrow$) Suppose there is an even length path between every two
vertices.  Since there is a path between every two vertices, the graph is
certainly connected.  Now supppose the graph was also bipartite.  On any
path in a bipartite graph, the successive vertices alternate colors. So if
the path has even length, the first and last colors will agree.  Since
every two vertices are connected by an even length path, every pair of
vertices has the same color.  In particular, the endpoints of any edge
must have the same color, a contradiction.  Hence the graph cannot be bipartite.

\noindent
($\Leftarrow$)
Suppose a connected graph has a pair of vertices $v \neq w$ such that
there is no path of even length between $v$ and $w$.  We will show that
the graph is bipartite.

Let $E$ be the set of vertices reachable by an even length path from $v$,
and let $O$ be the vertices reachable by an odd length path from $v$.  We
claim that coloring vertices in $E$ white and coloring vertices in $O$
black is a 2-coloring of the graph.

First of all we must show that this rule really defines a coloring.  Since
every vertex other than $v$ is reachable from $v$ by a path whose length
must be even or odd, every vertex besides $v$ gets assigned a color.  But
$v$ also gets a color: leaving and returning to $v$ using the same path in
both directions is an even length path from $v$ to $v$, so $v$ gets
colored white.

Moreover, every vertex will be assigned a unique color.  To verify this,
we must show that no vertex is in both $E$ and $O$.  But suppose $E$ and
$O$ had a vertex, $x$, in common.  This means there is an odd-length path,
$p_o$, and also an even length path $p_e$, each going from $v$ to $x$.
But because the graph is connected, there is also a path, $q$, from $x$ to
$w$.  Now the paths $p_oq$ and $p_eq$ both go from $v$ to $w$, and one of
them must be of even length, a contradiction.  So $E$ and $O$ are indeed
disjoint.

All that remains is to show is that there is no edge between distinct
vertices in $E$ nor between distinct vertices in $O$.  Suppose there was
an edge with endpoints $y \neq x$ which were both in $E$.  Then the even
length path from $v$ to $y$ followed by the edge $(y,x)$ is an odd length
path from $v$ to $x$, so $x$ is in $O$ as well as $E$, which we know is
impossible.  Similarly, there can't be an edge between two vertices in $O$.

So we have shown that the graph is bipartite. \qed

\iffalse

\bigskip\noindent{\bf Solution 2:}

Another solution to this problem was to argue that a graph has an
even-length path between every two nodes if and only if it is
connected and has an odd cycles.  This statement will follow from the
solution above and from the following theorem:
\begin{quote}
{\bf Theorem:} {\it
A graph is bipartite if and only if it has no odd cycles.}
\end{quote}
Here is the proof:

\noindent
($\Rightarrow$)

To say that a graph is bipartite is the same as to say that it is
2-colorable.  If $G=(V,E)$ is bipartite, then let $R,B$ (for red and
blue) $R\cap B=\emptyset, R\cup B=V$ be the two-coloring of $G$.  Take
any node $v_0$ in $V$, and any path $v_0,v_1,v_2,...,v_n,v_0$ that
goes from $v_0$ to $v_0$ (in other words, take any cycle in $G$).
Assume without loss of generality that $v_0\in{R}$.  Then it must be
that $v_i\in{R}$ if $i$ even and $v_i\in{G}$ if $i$ odd.  Hence $n$
must be odd and the length of the cycle is even.

\noindent
($\Leftarrow$)

We give a proof by induction on $n=|E|$, $n\geq{0}$.  The predicate we
will prove is the following: $P(n)=$``For every graph $G=(V,E)$ for
$|E|=n$, if $G$ has no odd cycles then $G$ is bipartite'':

\medskip
\noindent 
%
{\em Base case:} $P(0)$ is true because a graph with no edges is both
bipartite and has no odd cycles.

\medskip
\noindent 
%
{\em Inductive case:} Take some $n\geq{1}$.  We will show that if
$P(n-1)$ then $P(n)$.  Take some $G=(V,E)$ s.t. $|E|=n$.  Assume $G$
has no odd cycles.  Pick an edge $e=(v,u)\in{E}$ and remove it to
create a graph $G'=(V,E')$ where $E'=E\setminus\{e\}$.  Then $|E'|<n$
and $G'$ has no odd cycles, since $G$ did not have any.  Hence, from
$P(n)$ it follows that $G'$ is bipartite.  Let $R,B$ be a
two-coloring of $G'$.  We have two cases: First, if $u\in{R}$ and
$v\in{B}$ or vice versa, then the same $(R,B)$ is a two-coloring for
both $G'=(V,E')$ and $G=(V,E)$ and hence, in this case, $G$ is
bipartite.  The other case is if $u,v\in{R}$ (or $u,v\in{B}$, but
without loss of generality we can assume the former).  We have two
cases here:
\begin{enumerate}
\item
If $u$ and $v$ are not connected in $G'$ then we can invert the colors
in the connected (in $G'$) component $C\subseteq{V}$ to which $v$
belongs (and keep the colors of the vertices that do not belong to the
connected component $C$).  In result we will get another good
two-coloring of $G'$, but now $u$ and $v$ have a different color.
Hence this case looks like the one we looked at above.
\item
If $u$ and $v$ are connected in $G'$, then since they have the same
color in a two-coloring of $G'$, there is an even-length path between
them in $G'$.  But then adding an edge $(u,v)$ to $G'$ creates an
odd-length cycle, which contradicts the assumption that $G$ has no
odd-length cycles.
\end{enumerate}
\fi


\end{problemparts}

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

\problem {\bf (15 points)} A rooted tree is called \emph{finite-path} iff
it has no infinite simple paths starting at the root.

A finite-path tree need not be finite nor even have an upper bound on the
length of its paths.  For example, there is 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}.

\begin{figure}[htbp]
\centerline{\psfig{figure=figs/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}

Let $\preceq$ be the binary relation on rooted trees ``is (isomorphic to)
a proper subtree of.''  That is, $T_1 \preceq 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$.

\begin{problemparts}

\problempart Prove that $\preceq$ is a well-founded partial order on
finite-path trees.  (Use the definition of a partial order from Tutorial 3
which does not require that a partial order be reflexive).

\solution

We need to show that $\preceq$ is transitive and anti-symmetric:

\begin{itemize}
\item
$\preceq$ 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 $\preceq$ is anti-symmetric: 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.  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 in $T_1$, contradicting the assumption that $T_1$ is
finite-path.
\end{itemize}

Now we must show that $\preceq$ is well-founded.  Suppose not.  Then, as
shown in Handout 18 on well-founded posets, there must be an infinite
$\preceq$-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$.  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 $\preceq$ is a well-founded poset.  \qed


\problempart In Problem 7 of Problem Set 3, we established that for
any two-person game with a \emph{finite} game tree, at least one
player has a non-losing strategy.  Show that this result in fact holds
for all two-person games with a \emph{finite-path} game tree.

\solution

Problem 7(b) of Problem Set 3 established a stronger fact about game
trees: either one player has a winning strategy or both players have
nonlosing strategies.  In the solutions for Problem Set 3, the first
solution of 7(b) used induction on tree depth and so only applied to trees
of finite depth.  However, the second solution given for 7(b) only used
the fact that the ``proper subtree'' relation is a well-founded partial
order, and so it applies \emph{without change} to finite path trees.

\problempart Here is an example of a game.  Player one chooses a triple of
natural numbers.  Then players alternate choosing triples of natural
numbers.  Any triple may be selected as long as it is \emph{not}
coordinate-wise $\geq$ any previously selected triple.  The game ends
when a player picks the triple $(0,0,0)$; this player loses.

For example, player 1 might first choose (7,8,9).  Player 2 could then
choose (0,1,67), and after that Player 1 could choose (83, 0,0).  Player 2
can then choose (1,0,0).  Now player 1 can choose (0,0,1), allowing player
2 to choose (0,1,0).  This finally leaves player 1 with only the losing move
(0,0,0).

\iffalse In other words, if the first $n$ moves in the game are
$(x_1,y_1),(x_2,y_2),...,(x_n,y_n)$ where $(x_i,y_i)$ pairs with odd $i$'s
were picked by player A and those with even $i$'s were picked by player B,
then the next player (A if $n+1$ is odd or B if $n+1$ is even) can pick a
pair of natural numbers $(x_{n+1},y_{n+1})$ only if there is no $k$,
$1\leq{k}\leq{n}$ s.t. $x_{n+1}\geq{}x_k$ {\em and} $y_{n+1}\geq{}y_k$.\fi

Show that one of the players must have a winning strategy.  \hint Use the
results about well-quasi-orders from Tutorial 4.

\solution

In Problem 2 of Tutorial 4, we studied a more general version of the
game above, where the first player chose $n$, which sets up a
``dimension of the board they play on''.  The game above, is like the
game from Tutorial 4 where the first player always picks $n=3$, and so
all consequent moves are {\em triples} of natural numbers.  We can use
similar logic as in that problem to argue the following:
\begin{enumerate}
\item
Let's first cast the question of whether moves in this game are valid
or not in terms of some partial ordering in set $\naturals^3$:

A sequence $p_1,p_2,p_3,...,p_n$ (or an infinite sequence
$p_1,p_2,p_3,...$) of points in $\naturals^3$ (i.e. a sequence of
triples of natural numbers) is a {\em valid sequence of moves} in this
game (alternating moves of player A and player B), if and only if
\[
\forall(i,j)\,\, i<j \Rightarrow p_i \not\leq_3 p_j
\]
where relation $\leq_p$ is a partial order in $\naturals^3$ defined
as follows:
\[
(x_1,y_1,z_1) \leq_3 (x_2,y_2,z_2) ~~~\iff~~~
((x_1\leq{x_2})\wedge(y_1\leq{y_2})\wedge(z_1\leq{z_2}))
\]

\item
First note that $(\naturals,\leq)$ is a well-quasi-ordered set. Here is
a definition from Tutorial 4:
\begin{quote}
{\bf Definition 4.1:} {\it
A poset $(P,\preceq)$ is \emph{well-quasi-ordered} iff, for every infinite
sequence $p_1, p_2, \dots p_n \dots$ of elements in $P$, there are positive
integers $i<j$ such that $p_i \preceq p_j$.}
\end{quote}
The well-quasi-ordered property of $(\naturals,\leq)$ is immediate: any
infinite sequence of distinct natural numbers $n_1,n_2,n_3,...$ must
eventually include a number larger than $n_1$, and so must be a sequence
of the required kind.

\item
Now we can use the findings of Problem 2 in Tutorial 4 to argue that
set $(\naturals^3,\leq_3)$ is well-quasi-ordered.  We use Lemma 4.2 of
part (e) of Problem~2:
\begin{quote}
{\bf Lemma 4.2:} {\it
Suppose  $(P, \leq_P)$ and $(Q, \leq_Q)$ are well-quasi-ordered posets.
Then so is $P \times Q$ under the coordinate-wise partial order.}
\end{quote}
This lemma implies that since $(\naturals,\leq)$ is a
well-quasi-ordered poset by point (2) above, then so is $(\naturals^2,
\leq_2)$ where $\leq_2$ is a coordinate-wise partial order in
$\naturals^2$.  And applying the lemma once more, we get that
$(\naturals^3, \leq_3)$ is a well-quasi-ordered poset too.

\item
As in Part (e) of Problem 2, by bringing together point (1) and (3)
above, we realize that since $(\naturals^3,\leq_3)$ is
well-quasi-ordered, then in every infinite sequence of points
$p_1,p_2,p_3,...$ in $\naturals^3$, there must be a pair $(i,j)$,
$i<j$ s.t. $p_i\leq{p_j}$.  By point (1), this means that no infinite
sequence of points in $\naturals^3$ can be a sequence of valid moves
in this game.  Hence, every sequence of valid moves in this game is
finite (In particular, the game can never go on for ever).

\item
The fact that there can be no infinite sequence of valid moves in this
game means this game has a {\em finite-path} game tree.  Therefore,
the result from part (b) of this problem above applies here, i.e. one
of the players has a non-losing strategy.  But since there is no
``draw'' outcome in this game, a non-losing strategy must be a
winning strategy.

\end{enumerate}

\problempart \emph{Extra Credit}: Who has a winning strategy?  What is
the strategy?   \textbf{(We don't known the answer.)}

\iffalse
\stas{See what the students write and tell me if there are some
different strategies.  For $n=2$, there is a winning strategy for
player A: It should pick $(1,1)$ and then respond to every $(x,y)$
with $(y,x)$, unless $(x,y)=(0,0)$ and player B looses.  But I dont
see how to translate it into a 3-D strategy easily...  Please email
everyone if you see a light.}
\fi
\end{problemparts}





%END   Ray's problems

%BEGIN Ivan's problems (spring '98)
%END   Ivan's problems

%BEGIN George's problems
%END   George's problems

%BEGIN Josh's problems
%END   Josh's problems

%BEGIN Tina's problems
%END   Tina's problems

\end{problems)


\end{document}


