        \problemdata       % Takes 5 *mandatory* arguments
        {number-search-trees}             % latex-friendly label for the prob.
        {str. induction}  % The topic(s) of the problem content.
        {}               % Source (if known)
        {F01 tut5-2, S99 PS3, S01 tut3} %Usage (list ones you are aware of).
        {}        % Last revision info (author, date).

\begin{problem}
%\ignore'd by Joe 2/18--this could be a good problem
%but I think needs reworking. If we really want to make
%it correspond to the ``structural induction'' and recurs. structure
%definition stuff then the definition of the game tree should be more 
%formal with base cases and combination rules. Also, the way it's
%described now, since nodes correspond to situations in the game,
%it is a directed graph, not a tree.

Many two-person games in which players alternate moves---like
chess, checkers, and tic-tac-toe---can be represented abstractly by
\emph{game trees}.

The root of a game tree has children labeled with each of the possible
initial moves by the first player.  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 situation in the game, and its
children correspond to each of the possible moves by the player whose
turn it is in that situation.  The leaves of the tree correspond to
situations where no moves are possible---the game is over.  The leaves
are labelled with \emph{win}, \emph{lose}, or \emph{draw}, 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. \texttt{:-)})

A \emph{strategy} for a player in a game specifies which move the
player should make in any situation where 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.  Similarly, a
\emph{non-losing} stategy ensures that the player will \emph{win or
  draw} no matter what moves the other player makes.

For example, most elementary school children figure out non-losing
strategies in tic-tac-toe for \emph{both} the first and second players.
There is no winning strategy in tic-tac-toe for either player.  No one
knows if any player has a winning strategy for chess or checkers.
However, on general principles, we can be sure that at least one player
has a non-losing strategy.

More formally, let's define a family of Game Trees $T$ as follows:

1.  A single ``root'' node labeled with \emph{win}, \emph{lose}, or \emph{draw} is in $T$.

2.  An unlabelled root node connected to each element of a set of mutually disjoint game trees (not containing the root node either) called the ``immediate subgames'' of the game tree is in $T$.


\problempart Prove that for any two-person game with a finite game
tree, at least one of the players has a non-losing strategy.

\solution{
\begin{proof}
The proof is by structural induction on the game tree.
Let $P(T)$ be the proposition that for a game tree, $T$, at least one
of the players has a non-losing strategy.

{\bf Base case:}
For the base case of a single-node tree, the node is labeled \emph{win},
\emph{lose}, or \emph{draw}.  If the node is labeled \emph{win} or
\emph{draw}, then the first player has a non-losing strategy.  If
the node is labeled \emph{draw} or \emph{lose}, then the second
player has a non-losing strategy.  In both cases, there is a player with
a non-losing strategy.

{\bf Structural Induction Step:} In the inductive step, we want to prove
that for any game tree, $T$, if $P(T')$ holds for each immediate
subgame, $T'$, of $T$, then $P(T)$ holds.

So suppose $T$ is a game tree and there is a non-losing strategy for at
least one of the players for every immediate subgame, $T'$, of $T$.

Let $A$ be the player who moves first in the game defined by $T$, and
let $B$ be the player who moves second.  If player $B$ has a non-losing
strategy for \emph{every} subgame, $T'$, of $T$, then $B$ also has a
non-losing strategy for the full game tree $T$: no matter what move
player $A$ makes, player $B$ simply follows his non-losing strategy for
the immediate subgame determined by $A$'s move.

On the other hand, suppose there is some immediate subgame, $T_0$, of
$T$, for which player $B$ does not have a non-losing strategy.  
Since, by induction hypothesis, \emph{some} player has a non-losing
strategy for $T_0$, it must be player $A$ that the non-losing strategy
for this subgame.  But then player $A$ has a non-losing strategy for the
full game tree $T$: namely, make the move that leads to subgame $T_0$
and then pursue the non-losing strategy for that subgame.

In either case, at least one of the players has a non-losing strategy.
This completes the proof of the induction step, and thus the whole proof
by structural induction.

We conclude that $P(T)$ holds for all games trees, $T$.
\end{proof}
}

\problempart Conclude that either one player has a winning strategy or both
players have non-losing strategies.

\solution{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.  So in a game with no
draws, we conclude from part (a) that there is always a player with a
winning strategy.

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

\end{problem}
