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

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

\newcommand{\edge}[2]{(#1\text{---}#2)}

\begin{document} 
\inclassproblems{6, Wed.}

\begin{problem}
Two-person terminating games of perfect information are determined by
Recursive Game Trees (RGT) defined in the Appendix.  Prove:

\begin{theorem}\label{fund}
\textbf{Fundamental Theorem}: In every two-person terminating game of
perfect information, there is a winning strategy for one of the players.
\end{theorem}

\solution{
\begin{proof}
(Taken directly from Week 6 Notes.)

The proof is by structural induction on the definition of the RGT for the
game.  The induction hypothesis, $P(G)$ is that there is a winning strategy
for the game defined by $G$.

\textbf{Base case} ($G$ is a one node tree).  If the root of $G$ is
labelled \texttt{win}, then the first player has a winning strategy: don't
move.  If the root of $G$ is labelled \texttt{lose}, then the second player
has the same winning strategy.

\textbf{Inductive step} ($G$ has root $\mathbf{n}$ with edges to the roots
of a set, $\mathcal{G}$, of RGT's).  By structural induction hypothesis, we
may assume that for each $G' \in \mathcal{G}$, one player or the other has
a winning strategy.  We now consider two cases.

\emph{Case 1:} There is a tree, $G' \in \mathcal{G}$, with a winning
strategy for the second player.  Then there is a winning strategy for the
first player in game $G$: move first to the root of $G'$ and then follow
the winning strategy for the second player in the game defined by $G'$.

\emph{Case 2:} No tree in $\mathcal{G}$ has a winning strategy for the
second player.  Since by induction there is a winning strategy for each
tree in $\mathcal{G}$, it follows that there must be a winning strategy
for the first player in each of the games defined by trees in
$\mathcal{G}$.  Then there is a winning strategy for the second player in
game $G$: suppose the first player's initial move leads to the root of
some $G'\in \mathcal{G}$.  Then the second player will win by following
the winning strategy for the first player in the game defined by $G'$.

So in either case, one of the players has a winning strategy for $G$, that
is, $P(G)$ holds.

\end{proof}
}

\end{problem}

\instatements{\newpage}
\begin{problem}

\insolutions{
(This problem will be assigned in Problem Set 6; solutions will appear there.)
}

Prove by induction on the definition of planar drawing script (pds --- see
the Appendix) that

\bparts

\ppart Every face of a pds is a closed walk.
\iffalse

\solution{
The induction hypothesis is ``every face of $T$ is a closed walk,'' which
we prove by induction on pds, $T$.

\textbf{Base case} $T = (\lambda,\set{v})$.  The only face of $T$ is the
vertex, $v$, which is a closed walk of length zero, by definition.

\textbf{Inductive step}

Case 1. $T$ is obtained by attaching an edge, $\edge{v}{w}$ with a new
endpoint, $w$, to a face $\mathbf{x}$ of $S$ ending in vertex, $v$.  We
may assume by induction hypothesis that $\mathbf{x}$ is a closed walk,
which implies that it also begins with vertex, $v$, and that all the other
faces of $S$ are closed walks.

Then the faces of $T$ consist only of faces of $S$, which are closed
walks, and the new face $\mathbf{x}\, \edge{v}{w}\, w\, \edge{w}{v}$ which
is also a closed walk by definition, since $\mathbf{x}$ begins and ends
with $v$.

Case 2. $T$ is obtained by attaching a new edge, $\edge{v}{w}$ across a
face $(\mathbf{x}\ang{w}\mathbf{y})$, where $\mathbf{x}$ is a walk
beginning with $v$ and ending with $w \neq v$, and $\mathbf{y}$ is a walk
beginning with $w$ and ending with $v$.

Then the faces of $T$ consist only of faces of $S$, which are closed
walks, and the new faces
\begin{align}
\mathbf{x}\, \edge{w}{v}\, v,\label{vxw}\\
\mathbf{y}\, \edge{v}{w}\, w.\label{wyv}
\end{align}
But since $\mathbf{x}$ is a walk beginning with $v$ and ending with $w$, the
face~(\ref{vxw}) is a walk beginning and ending with $v$ and is therefore
closed.  Likewise, face~(\ref{wyv}) begins and ends with $w$, and is
therefore also a closed walk.}

\fi

\ppart Every edge of a pds appears once in exactly two faces, or twice
on one face, and nowhere else.
\iffalse

\solution{
The induction hypothesis is ``every edge that appears on a face of $T$,
appears once in exactly two faces, or twice on one face, and nowhere
else,'' which we prove by induction on pds, $T$.

\textbf{Base case} $T = (\lambda,\set{v})$.  There are no edges on the
single face of $T$, so the hypothesis is vacuously true.

Case 1. $T$ is obtained by attaching an edge, $\edge{v}{w}$ with a new
endpoint, $w$, to a face $\mathbf{x}$ of $S$ ending in vertex, $v$.  We
may assume by induction hypothesis that every edge of $S$ appears once in
exactly two faces, or twice on one face, and nowhere else.

Then the faces of $T$ are the same as faces of $S$, except that face
$\mathbf{x}$ is replaced by face $\mathbf{x}\, \edge{v}{w}\, w\,
\edge{w}{v}$.  So the only change in occurrences of edges is that a new
edge $\edge{v}{w}$ now appears twice on the new face of $T$ and nowhere
else.  Hence, $T$ satisfies the induction hypothesis.

Case 2.  Similar.
}
\fi

\eparts If $S$ is a pds with $v$ vertices, $e$ edges, and $f$ faces, then

\bparts 

\ppart  Euler's Formula:
\[
v-e+f =2.
\]

\ppart if  $e\geq 3$, then every face includes at least three distinct edges.

\eparts
\end{problem}

\instatements{\newpage}
\section*{Appendix}

\subsection*{Recursive Game Trees}
\begin{definition*}
\begin{enumerate}

\item A single node, $\mathbf{n}$, labelled \texttt{win} or \texttt{lose}
is an \emph{RGT} and its \emph{root} is $\mathbf{n}$.

\item 
If $\mathcal{G}$ is a nonempty finite or infinite set of pairwise disjoint
RGT's (that is, if $G_1\neq G_2 \in \mathcal{G}$, then $G_1$ and $G_2$ have
no nodes in common), and $\mathbf{n}$ is a ``new'' node not in any RGT in
$\mathcal{G}$, then the graph with an edge from $\mathbf{n}$ to the root of
$G$ for each $G \in \mathcal{G}$ is an RGT, and its root is $\mathbf{n}$.

\end{enumerate}

\end{definition*}

\subsection*{Planar Graphs}

A \emph{planar drawing script} (pds) defines how to draw a connected
simple graph in the plane.  It specifies the order in which to draw the
edges, and, as each edge is drawn, which face of the current drawing the
edge should go into.  It also specifies the one or two new faces that
result from adding the edge.  Here are the formal definitions:

A length $n$ {\em walk} in an undirected graph is an alternating sequence
of vertices and edges of the form:
\begin{equation}\tag{w}
v_0\ \edge{v_0}{v_1}\ v_1\ \edge{v_1}{v_2}\ v_2\ 
\dots\ \edge{v_{n-1}}{v_n}\ v_n
\end{equation}
A walk~(w) is \emph{closed} if $v_0 = v_n$.

A walk can cross itself, traverse the same edge multiple times, \etc A
length zero walk consists of a single vertex.

If $x$ is a walk of the form~(w) and $y$ is a length $k$ walk of the
form
\begin{equation*}
w_0\ \edge{w_0}{w_1}\ w_1\ \edge{w_1}{w_2}\ w_2\ 
\dots\ 
\edge{w_{k-1}}{w_k}\ w_k,
\end{equation*}
such that $v_n=w_0$, then we let $x\ang{v_n}y$, denote the length $n+k$ walk
\[
v_0\ \edge{v_0}{v_1}\ v_1\ \dots\ \edge{v_{n-1}}{v_n}\ v_n\
\edge{v_n}{w_1}\ w_1\ \edge{w_1}{w_2}\ w_2\ \dots\ \edge{w_{k-1}}{w_k}\ w_k.
\]

A \emph{planar drawing script} (pds), $S$, will consist of a list, $L_S$,
of edges and a set, $F_S$, of closed walks called the \emph{faces} of $S$.
A rightshift or reversal of any given closed walk is considered to define
the same face and the walk may be replaced by a rightshift or reversal as
convenient.\footnote{Formally, the face boundaries are cycles
\emph{represented} by walks.  We say two walks \emph{represent the same
cycle} iff either walk can be obtained from the other by a cyclic
rightshift or reversal.  The $k$th \emph{cyclic rightshift} of walk~(w) is
the walk
\begin{align*}
v_{k \text{\, mod\,} n+1}\ \edge{v_{k \text{\, mod\,} n+1}}{v_{k+1 \text{\, mod\,} n+1}}\ v_{k+1 \text{\, mod\,}
n+1}\ \edge{v_{k+1 \text{\, mod\,} n+1}}{v_{k+2 \text{\, mod\,} n+1}}\ v_{k+2 \text{\, mod\,} n+1}\\
\qquad \dots \edge{v_{n-1+k \text{\, mod\,} n+1}}{v_{n+k \text{\, mod\,} n+1}}\ v_{n+k \text{\, mod\,} n+1},
\end{align*}
and its reversal is
\[
v_n\ \edge{v_n}{v_{n-1}}\ v_{n-1}\ \edge{v_{n-1}}{v_{n-2}}\ v_{n-2}\ 
\dots\ 
\edge{v_1}{v_0}\ v_0.
\]}

Planar drawing scripts are defined recursively as follows:
\begin{enumerate}

\item $S_v \eqdef (\lambda, \set{v})$ is a pds.  That is $L_S $ is the
empty list, $\lambda$, and $F_S$ has only one face, namely, the length
zero walk consisting of the single vertex, $v$.

\item (Attaching an edge with a new endpoint to a face.)
 If $S$ is a pds,  $\mathbf{x}$ is face of $S$ ending in vertex, $v$,
  and $w$ is a ``fresh'' vertex not in any edge of $L_S$,
 then $T$ is a pds, where
\begin{eqnarray*}
L_T & \eqdef & L_S, \edge{v}{w}\\
F_T & \eqdef & (F_S - \set{\mathbf{x}}) \union
                        \set{\mathbf{x}\, \edge{v}{w}\, w\, \edge{w}{v}}.
\end{eqnarray*}

\item (Attaching an edge between two vertices on a face.)  Suppose $S$ is
a pds, $v$ and $w$ are distinct nonadjacent\footnote{That is,
$\edge{v}{w}$ is not in any face $S$.} of vertices, $\mathbf{x}$ is a walk
beginning with $v$ and ending with $w$, $\mathbf{y}$ is a walk beginning
with $w$ and ending with $v$, and $\mathbf{x}\ang{w}\mathbf{y}$ is face of
$S$.  Then $T$ is a pds, where
\footnote{There is one minor exception to this rule.  If $\mathbf{x}\,
\edge{w}{v}\, v$ and $\mathbf{y}\, \edge{v}{w}\, w$ turn out to be the
same face, then both ``copies'' of this face must appear in $F_T$.
Technically, this means that $F_T$ must be a multset rather than a set.
But the only situation in which this occurs is when there is only one face
and this face is a simple cycle---corresponding to a graph consisting of a
simple cycle that divides the plane into a single ``inside'' and a single
``outside'' region sharing the same boundary.  This exception is so
special that it is better handled in a footnote.}
\begin{eqnarray*}
L_T & \eqdef & L_S, \edge{v}{w}\\
F_T & \eqdef & (F_S - \set{\mathbf{x}\ang{w}\mathbf{y}}) \union
       \set{\mathbf{x}\, \edge{w}{v}\, v,\ \mathbf{y}\, \edge{v}{w}\,
w}.
\end{eqnarray*}
\end{enumerate}

\end{document}


\iffalse
A \emph{simple closed walk} is a walk in which $v_0=v_n$ and all other
vertices are distinct.  Closed walks are used to represent \emph{cycles} in
an undirected graph\footnote{Formally, we say two walks \emph{represent the
same cycle} iff either walk can be obtained by the other by a cyclic
rightshift or reversal.  The $k$th \emph{cyclic rightshift} of
walk~(w) is the walk
\[
v_{k \text{ mod } {n+1}}\ \edge{v_{k \text{ mod } \paren{n+1}}}{v_{k+1 \text{ mod } \paren{n+1}}}\ v_{k+1 \text{ mod } {n+1}}\ \edge{v_{k+1 \text{ mod } {n+1}}}{v_{k+2 \text{ mod } {n+1}}}\ v_{k+2 \text{ mod } {n+1}}\ 
\dots\ \edge{v_{n-1+k \text{ mod } {n+1}}}{v_{n+k \text{ mod } {n+1}}}\ v_{n+k \text{ mod } {n+1}}.
\]
The reversal of~(w) is the walk
\[
v_n\ \edge{v_n}{v_{n-1}}\ v_{n-1}\ \edge{v_{n-1}}{v_{n-2}}\ v_{n-2}\ 
\dots\ 
\edge{v_1}{v_0}\ v_0.
\]}.
\fi
