\problemdata                                                             
        {Game Trees} % latex-friendly label for the prob.
        {Strong Induction} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S01 Tutorial 3, 3} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
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.

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

\solution{\textbf{Solution:} The proof is by strong induction on the
  depth of the game tree.  Let $P(n)$ be the proposition that for a
  game tree of depth $n$, at least one of the players has a non-losing
  strategy.
  
  In the base case, a tree of depth 0 is a node 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 all three cases, the
  proposition $P(0)$ holds.
  
  In the inductive step, for $n \geq 0$ assume $P(1), P(2), \ldots,
  P(n)$ to prove $P(n+1)$.  A game tree of depth $n+1$ consists of a
  root joined to subtrees of depth at most $n$.  Let $A$ be the player
  making a move in the situation corresponding to the root node, and
  let $B$ be the other player.
  
  If player $B$ has a non-losing strategy for every subtree, then
  player $B$ has a non-losing strategy for the full game tree; no
  matter what move player $A$ makes, player $B$ is left with a game
  tree for which he has a non-losing strategy.
  
  On the other hand, if player $B$ lacks a non-losing strategy for
  some subtree, then by strong induction player $A$ has a non-losing
  strategy for the same subtree.  Furthermore, player $A$ has a
  non-losing strategy for the full game tree; namely, pick the subtree
  for which he has a non-losing strategy on his first move, and then
  pursue that non-losing strategy for the subtree.
  
  In either case, at least one of the players has a non-losing
  strategy.  This shows that $P(0), P(1), \ldots, P(n)$ imply $P(n+1)$
  and completes the proof by strong induction.}


\end{problem}
                                 