\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{\ms}[1]{\mathop{\text{#1}}}

\providecommand{\ide}{\ms{id}}
\providecommand{\EF}{\ms{F18}}
\providecommand{\T}{\ms{ST}}
\providecommand{\leaves}{\ms{leaves}}
\providecommand{\nodes}{\ms{nodes}}
\providecommand{\makeb}{\ms{makeboth}}
\newcommand{\membern}{\ms{member}}
\newcommand{\makeleft}{\ms{makeleft}}
\newcommand{\makeright}{\ms{makeright}}

\newcommand{\RBT}{\text{RecBinT}}
\newcommand{\FBT}{\text{FullBinT}}
\newcommand{\rt}{\text{root}}
%\newcommand{\rootr}{\text{FinT}}
\newcommand{\CT}{\text{CT}}
\newcommand{\RCT}{\text{RecCT}}

\newcommand{\deriv}{\frac{d}{dx}}
\renewcommand{\paren}[1]{\left(#1\right)}

%\newcommand{\setl}{L}
%\newcommand{\setlone}{L_1}
%\newcommand{\setltwo}{L_2}

%same as S02 cp5F

\begin{document} 
\inclassproblems{6, Mon}

\begin{problem} % F01, tut5

(Carried over from last Friday (Week 5).)

In Week 5 Notes we considered win-lose games, ignoring games which can end
in a draw.  Such games have finite-path game trees in which the leaves are
labelled with \emph{win}, \emph{lose}, or \emph{draw}, indicating the
outcome for the first player.

While a winning stategy for a player ensures the player will win no matter
what moves the other player makes, there is now the possibility of a
\emph{non-losing} stategy which ensures that the player will \emph{win or
draw} no matter what moves the other player makes.  (A winning strategy
counts as a kind of a non-losing strategy.)

For example, in tic-tac-toe there is no winning strategy for either
player, but \emph{both} players have non-losing strategies.  For chess, no
one knows if white or black has a winning strategy.  However, on general
principles, we can be sure that at least one player has a non-losing chess
strategy.

Explain why for any two-person win-lose-draw game with a finite path game
tree, either one player has a winning strategy or \emph{both} players have
non-losing strategies.

\solution{We could prove this the same way we proved the Fundamental
Theorem for win-lose games, using the well-foundedness of finite-path
trees under the ``strict-subtree'' partial order, but it's more elegant to
deduce this as a Corollary of the Fundamental Theorem.

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.

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{problem}

\instatements{\textbf{NOTE (October 7, 2002, 6PM):} There were two more
problems on the class handout that we didn't get to.}


\iffalse

\begin{problem}
The Elementary 18.01 Functions ($\EF$'s) are the set of functions of
one real variable defined recursively as follows:
\begin{enumerate}
\item The identity function, $\ide(x) \eqdef x$ is an $\EF$,\label{identfunc}

\item any the constant function is an $\EF$,\label{const}

\item $\sin, \cos, e^x$ are $\EF$'s,\label{basefunc} 

     and if $f,g$ are $\EF$'s, then so are

\item $f + g$, $f-g$, $fg$, $f/g$\label{+-}

\item the inverse function $f^{-1}$,\label{inversefunc}

\item the composition $f \compose g$.\label{cmp}
\end{enumerate}

Show that the Elementary 18.01 Functions are \emph{closed under taking
derivatives}.  That is, show that if $f$ is an $\EF$, then so is $df/dx$.

\solution{
\begin{proof}
By Structural Induction on def of $\EF$.
\begin{description}

\item[Base Cases:] We want to show that the derivatives of all the
functions mentioned in rules \ref{identfunc},\ref{const}, \ref{basefunc} are in $\EF$. This is easy: for
example, $\deriv \ide(x) = 1$ (constant) and so by rule \ref{const}, it is in
$\EF$. Similarly, $\deriv \cos(x) = -\sin(x)$ which is also in $\EF$
since $\sin(x)\in \EF$ by rule 3 and therefore $-\sin(x)$ as well (by
rule \ref{+-}). 

\item[Induction Case:] ($f^{-1}$).  Assume $df/dx \in \EF$ to prove
$\deriv f^{-1}(x) \in \EF$.  We know that $\deriv f^{-1}(x) =
1/(df/dx)$. Since $df/dx \in \EF$ (by assumption), so is $\frac{1}{df/dx}$ (by~\ref{+-}). 

\item[Induction Case:] ($f \compose g$).  Assume $df/dx, dg/dx \in \EF$
to prove $\deriv(f\compose g) \in \EF$. $\deriv(f\compose g)=\deriv
\paren{f(g)}=\frac{d}{dg}f(g)\cdot\frac{dg}{dx}$ which is in $\EF$  by~\ref{cmp}
and~\ref{+-}. The other cases are similar.
\end{description}
\end{proof}


}
\end{problem}

%%%%%%%%%%%%%%%%%%%%%%% PROBLEM %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5


\begin{problem}

\bparts

\ppart Give a recursive definition of the set of $\leaves$ of a $\RBT$.

\solution{We can then define the set of leaves, $L_T$, of $T \in \RBT$ as follows:
\begin{enumerate}

\item ($T=(V,E)$ has one vertex.)  $L_T \eqdef V$.

\item ($T = \makeleft(T_1)$.)  $L_T \eqdef L_{T_1}$.

\item ($T = \makeright(T_1)$.)  $L_T \eqdef L_{T_1}$.

\item ($T = \makeb(T_1,T_2)$.)  $L_T \eqdef L_{T_1} \union L_{T_2}$.

\end{enumerate}
}


Full Binary Trees, $\FBT$, are the special case of $\RBT$'s in which only
the $\makeb$ constructor is used.  For example,
Figure~\ref{fig:fullbintree} shows an FBT with 13 nodes of which 7 are
leaves:

\begin{figure}[h]
\begin{center}
\input{figures/fbtree.pic}
\end{center}
\caption{A full binary tree.}
\label{fig:fullbintree}
\end{figure}


\ppart Prove by structural induction on the definition of FBT
that for all FBT's, $t$,
\[
2\card{\leaves(t)} = \card{\nodes(t)}+1.
\]
\solution{
Let $T, t_1, t_2$ be FBTs. Let $L, \ell_1, \ell_2$ represent their
\emph{number} of leaves and similarly let
$N, n_1, n_2$ represent their number of nodes. We want to prove that for
all FBTs we have: $2L~=~N +1$
\begin{description}
\item[Base case:] When $N=1$ (the tree has only one vertex), then $L=1$
(it has one leaf) and so the claim is true ($2=1+1$). 
\item[Inductive step:] Assume that the claim holds for trees $t_1$ and
$t_2$. We want to prove that $T=\makeb(t_1, t_2)$ also satisfies that
property. We have:
\[
\left.\begin{array}{lll}
2\cdot \ell_1 &=& n_1+1\\
2\cdot \ell_2 &=& n_2+1
\end{array}\right\} \implies
2\cdot (\ell_1 +\ell_2) ~=~ (n_1+n_2+1)+1\implies
2\cdot L ~=~ N+1
\]
So the claim holds for $T$ as well.
\end{description}
}



\eparts
\end{problem}


\iffalse

%%%%%%%%%%%%%%%%%%%%%%% PROBLEM %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5

\begin{problem} 
We define the family $\T$ of \emph{search trees} as follows:
\begin{enumerate}
\item  Any single number $x$ is 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
$\makeb(T,x,T')$ formed by attaching a left-pointing arrow from $x$ to
$T$ and a right-pointing arrow from $x$ to $T'$ is also in $\T$. See
Figure \ref{fig:searchtree}
\end{enumerate}

\begin{figure}[h]
\begin{center}
\input{figures/cp5F-searchtree.latex}
\end{center}
\caption{Creating a new search tree by applying rule 2}
\label{fig:searchtree}
\end{figure}


The number $x$ is called the \emph{root} of the tree that is formed.

\begin{problemparts}

\problempart Draw all the different search trees in $\T$ that have nodes
1, 2, 3, 4, 5.


\solution{
See Figure \ref{fig:possibilities}
%(1 2 (4 3 5)) and ((1 3 2) 4 5).

\begin{figure}[h]
\begin{center}
\input{figures/cp5F-st.latex}
\end{center}
\caption{The two possible search trees}
\label{fig:possibilities}
\end{figure}

}

\ppart
Define a function $\membern:\naturals \cross \T \to \set{0,1}$
recursively as follows:
\begin{eqnarray}
\membern(n,n)  & \eqdef & 1,\\
\membern(n,m)  & \eqdef & 0, \text{ for } n \neq m \in \naturals,\\
\membern(n,\makeb(T,n,T')) & \eqdef & 1,\\
\membern(n,\makeb(T,m,T')) & \eqdef & \membern(n,T)) \text{ for } n < m,\label{mn<}\\
\membern(n,\makeb(T,m,T')) & \eqdef & \membern(n,T')) \text{ for } n > m.
\end{eqnarray}

Prove that
\[
\membern(n,T) = 1 \iff n \in \nodes(T).
\]

\solution{
\begin{proof}
Note that we are asked to prove \emph{both} directions! ($\iff$). The
proof will be by structural induction on the definition of $\T$. 
\begin{description}
\item[Base Case:] $|T|=1$. The tree has only one node
representing a natural number $t$. 
\begin{description}
\item[($\Longleftarrow$)]If $n\in \nodes(T)$ then $n=t$ and so by rule
(1), $\membern(n,t)=1$.
\item[($\Longrightarrow$)]If $\membern(n,t)=1$ then, by rule (2), it is
impossible to have  $n\neq t$ because in that case
$\membern(n,t)=0$. Therefore, $n=t$ and so $n \in \nodes(T)$
\end{description}

\item[Induction Step:] There is only one operation to consider, namely $\makeb(T,x,T')$. Assume that
\begin{eqnarray*}
\membern(n,T) = 1 \iff n \in \nodes(T),\label{mnT}\\
\membern(n,T') = 1 \iff n \in \nodes(T')
\end{eqnarray*}
to prove
\begin{equation*}
\membern(n,\makeb(T,x,T')) = 1 \iff n \in \nodes(\makeb(T,x,T')).
\end{equation*}
\begin{description}
\item[Case 1: ($n = x$)] Then, by the definiton of ``nodes'' $n \in
\nodes(\makeb(T,x,T'))$. At the same time, $\membern(n,\makeb(T,x,T')) = 1$ by definition of
$\membern$. Notice that there is no if-then statement here. If $n=x$
then both sides of the double implication ($\iff$) have to be true.

\item[Case 2: ($n < x$)] Then $n \in \nodes(\makeb(T,x,T'))$ iff $n \in \nodes(T)
\union \nodes(T')$ by definition of $\nodes$.  But since $\makeb(T,x,T')
\in \T$, we know $x < \min(\nodes(T'))$, so $n \notin \nodes(T')$.
Therefore, $n \in \nodes(\makeb(T,x,T'))$ iff $n \in \nodes(T)$.
By~(\ref{mnT}), $n \in \nodes(T)$ iff $\membern(n,T) =1$.  But
$\membern(n,\makeb(T,x,T')) = \membern(n,T)$ by~(\ref{mn<}), completing
the proof.

\item[Case 3: ($n > x$)] Symmetric to Case 2.
\end{description}
\end{description}
\end{proof}
}

\end{problemparts}
\end{problem}
\fi


\section{Appendix: From Week 6 Notes}


Several basic examples of recursively defined data types are based on
\emph{rooted trees}.  These are possibly infinite directed trees, $T =
(V_T, E_T)$, with a necessarily unique ``root'' vertex $\rt(T)$, such that
every vertex is reachable by a directed path from the root.  Finite-Path
Trees from
\hyperref{http://theory.lcs.mit.edu/classes/6.042/fall02/handouts/lectures/ln5.pdf}
{def}{fptree}{Week 5 Notes}, for example, are the class of rooted trees
which do not have any infinite directed path from the root.

Another important class of trees are the \emph{ordered binary trees}.
These are possibly infinite rooted trees with labelled edges, such that at
most two edges leave each vertex.  If two edges leave a vertex, one is
labelled \texttt{left} and the other is labelled \texttt{right}.  If one
edge leaves a vertex, it is labelled either \texttt{left} or
\texttt{right}.

\begin{example}
We will define a special class of ordered binary trees called the \emph{recursive
ordered binary trees}, $\RBT$:

\begin{enumerate}

\item
If $G$ is a graph with one vertex and no edges, then $G$ is a $\RBT$.
That is, $(\set{v}, \emptyset) \in \RBT$ and $\rt((\set{v}, \emptyset)) =
v$.

\item \label{ml}
If $T=(V,E)$ is in $\RBT$, and $\mathbf{n}$ is a ``new'' node not in $V$,
then the graph, $\ms{makeleft}(T)$, made by adding an edge labelled
\texttt{left} from $\mathbf{n}$ to $\rt(T)$ is a $\RBT$.  That is,
\[
\ms{makeleft}(T) \eqdef (V \union \set{\mathbf{n}}, E \union
 \set{(\mathbf{n},\rt(T),\texttt{left})}) \in \RBT,
\]
where $(v,w,\ell)$ is the directed edge from vertex $v$ to
vertex $w$ with label $\ell$.

\item \label{mr} Same as above, with ``right'' in place of ``left.''

\item If $T_1=(V_1,E_1)$ and $T_2=(V_2,E_2)$ are in $\RBT$, $V_1$ and
$V_2$ are disjoint, and $\mathbf{n}$ is a ``new'' node not in $V_1 \union
V_2$, then the graph, $\ms{makeboth}(T_1,T_2)$, made by adding an edge
labelled \texttt{left} from $\mathbf{n}$ to $\rt(T_1)$ and an edge
labelled \texttt{right} from $\mathbf{n}$ to $\rt(T_2)$ is a $\RBT$.
That is,
\end{enumerate}

\[
\ms{makeboth}(T_1,T_2) \eqdef (V_1 \union V_2 \union \set{\mathbf{n}}, E_1
\union E_2 \union \set{(\mathbf{n},\rt(T_1),\texttt{left}),
(\mathbf{n},\rt(T_2),\texttt{right})}) \in \RBT.
\]

These cases are illustrated in Figure~\ref{fig:bintree}, with edges
labelled ``left'' shown going down to the left, and edges labelled
``right'' shown going down to the right.

\begin{figure}
\begin{center}
\input{figures/btree.pic}
\end{center}
\caption{Building a binary tree: (a)~$\ms{makeleft}(T)$,
(b)~$\ms{makeright}(T)$, and (c)~$\ms{makeboth}(T_1,T_2)$.}
\label{fig:bintree}
\end{figure}
\end{example}

A special case of $\RBT$'s are the \emph{full} ordered binary trees,
$\FBT$.  These are $\RBT$'s in which every node is either a \emph{leaf}
(\ie has out-degree zero) or has both a left and right subtree (see
Figure~\ref{fig:fullbintree}).  In other words rules~\ref{ml}.\
and~\ref{mr}.\ in the definition of $\RBT$ are not used in defining the
subset $\FBT \subset \RBT$.

\fi

\end{document} 
