\documentclass[12pt,twoside]{article}
\input{macros-course}

%% Latex asks whether or not to include solutions
\askaboutsolutions


\begin{document}

%% TUTORIAL 5: Trees, Structural Induction (Rad, Fall01)
\ifshowsolutions
  \tutsol{5}{October 4, 2001}{\stamp}
\else
  \tutprobn{5}{October 4, 2001}{\stamp}
\fi

% Other possibilities
% S01 tut2: binary tree false proof
% S01 pset3: string reversal, numbered search trees
% More ambitiously, extend game tree idea...

\begin{problems}

%------------------------------------------------
% source: pset fall00
% topic: structural induction, strings, proofs
% last used: karger s01 pset3
\def\T{\cal N}

\problem We define the family $\T$ of number search trees as follows:
\begin{enumerate}
\item
  Any single number $x$ is in $\T$.
\item If $T$ is in $\T$, and $x$ is a number greater than any number
  in $T$, then the structure formed by pointing an arrow
  labelled ``left'' from $x$ to $T$ is also in $\T$.
n\item If $T$ is in $\T$, and $x$ is a number smaller than any number
  in $T$, then the structure formed by pointing an arrow
  labelled ``right'' from $x$ to $T$ is also in $\T$.
\item If $T$ and $T'$ are in $\T$, and a number $x$ is larger than
  every number in $T$ but smaller than every number in $T'$, then the
  structure formed by attaching an arrow labelled ``left'' from $x$
  to $T$ and an arrow labelled ``right'' from $x$ to $T'$ is also in
  $\T$.
\end{enumerate}
In all cases above, the number $x$ is called the \emph{root} of the
tree that is formed.  Since the descriptions above are wordy, you may
wish to introduce some notation, like makeleft$(T,x)$ to denote the
thing built up according to the first recursive rule.  Likewise,
makeright$(x,T)$, makeboth$(T,x,T')$.

\ppart How many different number search trees with four nodes will be
in $\T$ if our domain consists of the numbers 1, 2, 3 and 4?  Give an
example of how one such tree might be constructed using the structural
definition.

\solnospace{Consider the number search tree with each number at the
root.  If 1 is at the root, 2, 3 and 4 must be to its right.  There
are five different number search trees that can be made with 2, 3 and
4, so there are three different trees that can be made with 1 at the
root.  If 2 is at the root, 1 must be to its left, and 3 and 4 to its
right.  Since there are two different number search trees that can be
made with 3 and 4, there are two different trees that can be made with
2 at the root.  When 3 is at the root, the case is very similar to 2,
and when 4 is at the root, the case is very similar to 1.  This means
there are 14 number search trees that can be made containing all of
the numbers 1, 2, 3 and 4.
\begin{center}
\begin{picture}(60,80)
\put(7,45){1}
\put(10,40){\circle*{3}} \put(10,40){\line(1,1){20}}
\put(27,65){2}
\put(30,60){\circle*{3}} \put(30,60){\line(1,-1){20}}
\put(47,45){4}
\put(50,40){\circle*{3}} \put(50,40){\line(-1,-2){10}}
\put(30,20){3}
\put(40,20){\circle*{3}}
%\put(10,40){\circle*{3}} %\put(10,40){\line(2,3){20}}
%\put(30,10){\circle*{3}}
\end{picture}\\
An example of a number search tree for the numbers 1, 2, 3 and 4.
\end{center}
}

Now consider the following recursive algorithm for checking whether a
certain number is present in a tree $T$.
\begin{tabbing}
else\=else\=else\=else\=\kill

Algorithm Member$(q,T)$\\
\\
\>Let $x$ be the root of tree $T$\\
\> {\bf if} $x=q$ {\bf then}\\
\> \> {\bf return} YES\\
\> {\bf else} \\
\> \> {\bf if} $q<x$ {\bf and} $x$ has a ``left'' arrow to tree $T'$ {\bf
  then}\\
\> \> \> {\bf return} Member$(q,T')$\\
\> \> {\bf else if} $q>x$ {\bf and} $x$ has a ``right'' arrow to tree $T'$ {\bf
  then}\\
\> \> \> {\bf return} Member$(q,T')$\\
\> \> {\bf else}\\
\> \> \> {\bf return} NO\\
\end{tabbing}

\ppart Prove that a call to member$(q,T)$ returns YES if and only if
$q$ is a number in the number search tree $T$.

\newcommand{\membern}{\hbox{member}}
\newcommand{\makeleft}{\hbox{makeleft}}
\newcommand{\makeright}{\hbox{makeright}}
\newcommand{\makeboth}{\hbox{makeboth}}

\solution{ We use structural induction. We use $x<T$ to mean
  $x<\mbox{all numbers in }T$, and define $x>T$ similarly. We get four
  cases, one for each production rule.
\begin{enumerate}
\item
For a single-node tree $T$ with root $x$, if $q\in T$, $q=x$ and 
$\hbox{member}(q,T)$ returns YES. If $q\notin T$, since there are no arrows
from $x$, the final else is taken and $\hbox{member}(q,T)$ returns NO.
\item
Fix $T$, and assume $\forall q$, $\hbox{member}(q,T)$ returns YES iff $q\in T$.
We need to show that $\forall q,\forall x>T$,
$\membern(q,\makeleft(T,x))$ returns YES iff $q\in\makeleft(T,x)$.
If $q\in\makeleft(T,x)$, $q=x$ or $q\in T$. If $q=x$,
$\membern(q,\makeleft(T,x))$ immediately returns YES. If $q\in T$, $q<x$
and since $x$ has a left arrow to $T$, $\membern(q,T)$ is returned,
which is YES by inductive assumption. If $q\notin\makeleft(T,x)$, then
$q\ne x$ and $q\notin T$, so either the final else is taken and NO
returned or $\membern(q,T)$ is returned, returning NO by inductive
assumption.
\item
Similar to 2.
\item
Fix $T$, $T'$ and assume $\forall q$, $\membern(q,T)$ returns YES iff
$q\in T$ and $\membern(q,T')$ returns YES iff $q\in T'$. We need to
show that $\forall q$, $\forall x\suchthat x>T\wedge x<T'$,
$\membern(q,\makeboth(T,x,T'))$ returns YES iff
$q\in\makeboth(T,x,T')$. If $q\in\makeboth(T,x,T')$, there are 3
cases. Case 1: $q=x$, so member returns YES. Case 2: $q\in T$, so
$q<x$, $x$ has a left arrow to $T$, and $\membern(q,T)$ is returned,
which is YES by inductive assumption. Case 3: $q\in T'$, by similar
reasoning YES is returned. If $q\notin\makeboth(T,x,T')$, then $q\ne
x$, $q\notin T$, and $q\notin T'$, so either NO is returned
immediately or $\membern(q,T)$ or $\membern(q,T')$ is returned, which
are NO by inductive assumption.
\end{enumerate}
}


%------------------------------------------------
% source: spring 99, pset 3
% topic: structural induction, list
% last used: karger spring 01 tut3

%\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.

\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.

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$.


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

\solnospace{
\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}
}

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

\solnospace{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}
}

%---------------------------------------------------------
% source: spring00 ps4
% topic: bipartite, tree, 2 coloring
% redone to add structral induction

\problem A 2-colorable graph is called {\em bipartite}.  Prove by
induction that every unordered unrooted tree is bipartite. The set of
{\em unordered unrooted} trees $T$ is defined recursively as follows:

1.  A single node is in $T$.

2.  If $t_1$ and $t_2$ are two disjoint trees in $T$, then the tree
    $t'$ formed by adding an edge from any vertex $v$ of $t_1$ to any
    vertex $u$ of $t_2$, is also in $T$.

\solnospace{
\begin{proof}
We want to prove that a tree is 2-colorable.  If we do this, then we
have shown that a tree is bipartite.  We will prove this using
structural induction.

{\bf Base case:} The base case is trivially true.  A single node can be
colored with just one color, meaning that it is two-colorable, and
therefor bipartite.

{\bf Structural Induction Step:}
Using rule 2 in the definition of an unordered,
unrooted tree, any tree is constructed out of two smaller trees, $t_1$
and $t_2$. Each of these trees, by our inductive hypothesis, is 2-colorable.
Can we join $u$ from $t_1$ and $v$ from $t_2$ in a way such that our
new tree is also 2-colorable?  To do this, $u$ and $v$ must be
different colors.

Consider a 2-coloring of each of the smaller trees.  If vertex $v$
is a different color from $u$, then we can connect the
two trees to form the larger tree, and we are done.  If they are
different colors, then switch the coloring in $t_2$.  Now $u$ and $v$
are different colors, and can be connected.  Thus all possible trees
that can be constructed using the recursive definition must be 2-colorable.
\end{proof}
}

\end{problems}

\section*{Appendix}
\subsection*{Tutorial 4, Problem 2}
\begin{problems}
\problem
%-----------------------------------------------------------------%
% source: not sure, also has been used for many terms as a tutorial problem
% topic: graphs, false proofs

Let $L_n$ be the $n+1$-vertex simple ``line'' graph consisting of a
single simple path of length~$n$.  For example, $L_4$ is shown in the
figure below:

\begin{figure}[h]
\begin{center}
\begin{picture}(80,30)
\put(00,15){\circle*{3}} \put(00,15){\line(1,0){20}}
\put(20,15){\circle*{3}} \put(20,15){\line(1,0){20}}
\put(40,15){\circle*{3}} \put(40,15){\line(1,0){20}}
\put(60,15){\circle*{3}} \put(60,15){\line(1,0){20}}
\put(80,15){\circle*{3}}
\end{picture}
\end{center}

\centerline{The line graph $L_4$}
\end{figure}

Let's say a simple graph has ``two ends'' if it has exactly two
vertices of degree~one, and all its other vertices have degree~two.
In particular, for $n \ge 1$, the graph~$L_n$ has two ends.

\problempart
Draw a diagram of the smallest simple graph with two ends which is not
isomorphic to any line graph.
%\hint See part (d).

%%  What is the smallest $n \ge 1$ such that there is an
%%  $n+1$-vertex simple graph with two ends which is \emph{not} isomorphic
%%  to~$L_n$? \hint See part (d).\brule{2em}

\solnospace{
\begin{center}
\begin{picture}(80,30)
\put(00,15){\circle*{3}} \put(00,15){\line(1,0){20}}
\put(20,15){\circle*{3}}
\put(40,15){\circle*{3}} \put(40,15){\line(1,0){40}}
\put(60,35){\circle*{3}} \put(40,15){\line(1,1){20}}
\put(80,15){\circle*{3}} \put(80,15){\line(-1,1){20}}
\end{picture}\\
The smallest two-ended graph not isomorphic to any line graph.
\end{center}}

\problempart
Explain briefly, but clearly, what is wrong with the following
argument:

\paragraph{False theorem:}
Every simple graph with two ends is isomorphic to~$L_n$ for some~$n~\ge~1$.

\paragraph{False proof:}
We prove by induction on the number, $n \ge 1$, of edges in a simple
graph, that every two-ended graph with $n$ edges is isomorphic
to~$L_n$.

(Base case $n = 1$): A simple graph with one edge can only consist of
the two vertices connected by that edge and some number of vertices
not attached to  any edge, i.e., vertices of degree~zero.  Since a
two-ended graph cannot have vertices of degree~zero, the only
two-ended graph with one edge must consist solely of the two vertices
connected by the edge, which makes it isomorphic to~$L_1$.

(Induction case): Assume that $n \ge 1$ and every two-ended graph with
$n$ edges is isomorphic to~$L_n$.  Now let $G_n$ be any two-ended
graph with $n \ge 1$ edges.  By hypothesis, $G_n$ is isomorphic
to~$L_n$.  Suppose an edge is added to~$G_n$ to form a two-ended
graph~$G_{n+1}$.

Since $G_n$ is isomorphic to~$L_n$, it consists of a simple path of
length~$n$.  The only way to add an edge to the path and preserve
two-endedness is to have that edge go from one end---that is, one of
the degree-one vertices---to a new vertex, lengthening the path by
one.  That is, the resulting $n+1$-edge graph must be a simple path of
length~$n + 1$, so it is isomorphic to~$L_{n+1}$.  Q.E.D.

\solnospace{
The inductive case is argued in an incorrect way.  The inductive case
must consist of a proof for any $n\ge{1}$ that if $G_{n+1}$ is
two-ended then $G_{n+1}\sim L_{n+1}$ ($A\sim{B}$ is a notation for ``$A$
is isomorphic to $B$''), using the assumption that for every two-ended
$G_n$, $G_n\sim{L_n}$ (alternatively, in strong induction, we can use
an assumption that for every $k$, $1\ge{k}\ge{n}$, if $G_k$ two-ended
then $G_k\sim{L_k}$).

The false proof above does not argue that at all.  Instead, it states
that if one takes a two-ended $G_n$ which is isomorphic to $L_n$, and
extends it by an edge to form a two-ended $(n+1)$-edge graph $G'$,
then $G'\sim{L_{n+1}}$.  This is true, but to transform this argument
into an inductive proof, one would have to argue that every two-ended
$(n+1)$-edge graph $G_{n+1}$ can be formed in this way, i.e. by adding
another edge to some two-ended graph $G_n$.  However, this cannot be
argued because it is not true.  For example, in the solution to part
(a), we have a two-ended graph $G_4$ which cannot be formed by adding
an edge to some two-ended $G_3$.
}

\problempart
Here is another argument for the same False Theorem as in part~(b).
Explain exactly where it goes wrong.
\paragraph{False proof 2:}
Same induction hypothesis and base case as in part~(b).

(Induction case): For any $n\geq 1$, let $G_{n+1}$ be any two-ended graph
with $n+1$ edges.  Let $G_n$ be the graph which results from removing one
of the degree-one vertices~$v$ of~$G_{n+1}$ and the edge~$\{v,w\}$
attached to it.  So $G_n$ no longer has the vertex, $v$, of degree~one.
But the degree of $w$ is one less in~$G_n$ than it was in~$G_{n+1}$, so
$G_n$ still has two vertices of degree~one and one fewer vertex of
degree~two.  Therefore $G_n$ is also two-ended.  By induction $G_n$
consists of a simple path of length~$n$.  But $G_{n+1}$ is obtained by
attaching an edge from one end of the path to a vertex~$v$ not on the
path, thereby lengthening the path by one.  So $G_{n+1}$ is isomorphic to
a simple path of length~$n+1$; that is, it is isomorphic to~$L_{n+1}$.
Q.E.D.

\solnospace{
The claim
\begin{quotation}\noindent
$G_n$ still has two vertices of degree~one and one fewer vertex of
degree~two.
\end{quotation}
is wrong.  The degree of $w$ is one less
in~$G_n$ than it was in~$G_{n+1}$, hence it can be equal to one if it
was two in $G_{n+1}$, but it can also be equal to zero if it was one
in $G_{n+1}$.  The false proof above is wrong because it ignores this
this second possibility.  For example, if we take $G_{n+1}=G_4$ from
the solution to part (a):\\
\begin{center}
\begin{picture}(80,30)
\put(00,15){\circle*{3}} \put(00,15){\line(1,0){20}}
\put(20,15){\circle*{3}}
\put(00,20){w}
\put(20,20){v}
\put(40,15){\circle*{3}} \put(40,15){\line(1,0){40}}
\put(60,35){\circle*{3}} \put(40,15){\line(1,1){20}}
\put(80,15){\circle*{3}} \put(80,15){\line(-1,1){20}}
\end{picture}\\
Graph $G_{n+1}$
\end{center}
We see that if you remove $v$ then $w$ will have degree zero in a
resulting graph $G_n$:
\begin{center}
\begin{picture}(80,30)
\put(00,15){\circle*{3}}
\put(00,20){w}
\put(40,15){\circle*{3}} \put(40,15){\line(1,0){40}}
\put(60,35){\circle*{3}} \put(40,15){\line(1,1){20}}
\put(80,15){\circle*{3}} \put(80,15){\line(-1,1){20}}
\end{picture}\\
Graph $G_{n}$
\end{center}
Obviously, $G_n$ is not two-ended.}

\problempart
Describe how to make a small revision to one of the false proofs above
so that it becomes a correct proof of the theorem ``Every
\emph{connected} simple graph with two ends is isomorphic to~$L_n$ for
some~$n \ge 1$.''

\solnospace{
The proof in part (c) can be easily fixed if the graphs are connected,
because then the quoted false claim will be true.  Here is an
example of how one could inject into the proof from part (c) an
argument justifying the claim for the case of connected
graphs:
\begin{quotation}
[...But the degree of $w$ is one less in~$G_n$ than it was in~$G_{n+1}$.]
Since $G_{n+1}$ was two-ended, $w$ must be of degree either one or two
in $G_{n+1}$.  However, it cannot be of degree one because then
vertices $v$ and $w$ would be connected only to each other and
disconnected from the rest of the graph, which would contradict the
assumption that $G_{n+1}$ is connected.  Therefore, $w$ must have
degree two in $G_{n+1}$, and hence has degree one in $G_n$.
Hence, [ $G_n$ still has two vertices of degree~one and one fewer
vertex of degree~two.  Therefore...]
\end{quotation}

The false proof in part (b) cannot be easily fixed.  If we tried to
use its structure to prove that all connected two-ended graphs are
linear graphs, we would have to supply the argument that every
connected two-ended graph can be formed by adding an edge to some
connected two-ended graph with one less edge.  To argue that would be
as complicated as the above proof.
}

\end{problems}
\end{document}











