\documentclass[12pt,twoside]{article}

%\usepackage{amsmath}

\input{../handouts/macros-course}

%\def\cent{{\not\!\mathrm{c}}}
\renewcommand{\implies}{\longrightarrow}


%\newcommand{\solution}[1]{}
%\newcommand{\solution}[1]{\bigskip {\bf Solution:}\\ #1\bigskip}
\askaboutsolutions

\begin{document}
% No Mini-Quiz this week due to diagnostic
%\handout{tut3}{Mini-Quiz 3}{February 23, 2001}
%\begin{enumerate}
%\item Write your name:
%\item (Rosen section 1.4 problem 5)  For each of the following sets, determine whether 2 is an element of that set
%\bparts
%\ppart $\{ x \in \reals  |$  x is an integer greater than 1$\}$
%\ppart $\{ x \in \reals  |$  x is the square of an integer$\}$
%\ppart $\{ 2, \{2\} \}$
%\ppart $\{\{2\},\{\{2\}\}\}$
%\ppart $\{\{2\},\{2,\{2\}\}\}$
%\ppart $\{\{\{2\}\}\}$
%\eparts
%\end{enumerate}
%\newpage

%\thispagestyle{empty}

%\mbox{}

%\setcounter{page}{0}

%\newpage

\handout{tut3}{Tutorial 3 Problems}{February 23, 2001}


\begin{problems}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\makelist}{\mathop{\mbox{makelist}}}
\newcommand{\head}{\mathop{\mbox{head}}}
\newcommand{\tail}{\mathop{\mbox{tail}}}
\newcommand{\findMin}{\mathop{\mbox{findMin}}}
\problem Consider the following recursive definition of the
set~$\mathcal{L}$ of lists containing real numbers:
\begin{enumerate}
\item
The empty list, $nil$, is in $\mathcal{L}$.
\item
If $t \in \mathcal{L}$, then $\forall x \in \reals$,
$\makelist(x,t) \in \mathcal{L}$.
\end{enumerate}

Conceptually, $\makelist(x,t)$ makes a new list with $x$ as its first element,
and $t$ as the rest of the list.
Two helpful list functions are
$\head()$ and $\tail()$. We define $head()$ such that
$\head(nil) = nil$ and $\head(\makelist(x,t)) = x$.  Tail is defined
as $\tail(nil) = nil$ and $\tail(\makelist(x,t)) = t$.  

Construct a recursive algorithm in terms of these functions
that finds the minimum element of a non-empty
list in~$\mathcal{L}$ and prove that the algorithm is correct. (If
there are several minimal elements, the algorithm only needs to find
one of them.)

\solution{%
  \textbf{Solution:}
%  The algorithm uses the to operators $\head$ and
%  $\tail$. Given a list~$L$, $\head(L)$ returns the first element of the
%  list and $\tail(L)$~returns the list formed by removing the first
%  element of~$L$. The empty list is denoted by~$\emptyset$.
  \begin{trivlist} \parskip=0pt \parsep=0pt
  \item Algorithm $\findMin(Y)$.
  \item\qquad \textbf{if} $\tail(Y) = nil$ \textbf{then} return $\head(Y)$,
  \item\qquad \textbf{else} return $\min\{\head(Y), \findMin(\tail(Y))\}$.
  \end{trivlist}
  Note that we do not have to check for empty lists in this algorithm,
  as we only claim that the algorithm is correct on {\em non-empty} lists.
  In a real program, you would want such a check for robustness,
  but this is not a class in real-world defensive programming techniques.

  \begin{theorem*}
    The above algorithm terminates and returns the minimum element of
    its argument when its argument is a non-empty list in $\mathcal{L}$.
  \end{theorem*}

  \begin{proof}By structural induction on $\mathcal{L}$

  {\em Base Case:}
  If $Y$ is a list of the form $\makelist(x,nil)$,
  then $x$ is the minimum (and only) element of the list. In this
  case, our algorithm returns $\head(\makelist(x,nil))$ (which is $x$).
  So in this base case,
  the algorithm terminates, returning the minimum element of the
  non-empty list argument $Y$.

  {\em Inductive Step:}
  Assume the algorithm terminates, returning the minimum element
  for a list $t$ in $\mathcal{L}$.
  Also, assume that we follow the \textbf{else} branch of the code
  since the termination and correctness of the \textbf{if} branch
  are covered in the base case.

  The minimum of a list is the lesser of its first element and
  the minimum of the rest of the list. Since (by inductive assumption), our
  algorithm terminates correctly on $t$, our algorithm also terminates
  correctly on $\makelist(x,t)$ for all $x \in \reals$ since it
  returns the smaller of $x$ and $findMin(t)$.

  The base case and inductive step prove (by structural induction)
  that on any non-empty list $Y$ in $\mathcal{L}$, our algorithm terminates and
  returns the minimum element of $Y$.
  \end{proof}
  }

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%
% Maybe this problem was a bit too hard? I think that the problem of
% proving formally that the matrix representation of S o R is the
% product of M_R and M_S with \land instead of \times and \lor
% instead of + may be better. This makes the students understand
% what the composition is and it also introduces notation like
% \bigvee, which can be defined recursively, and we could make
% them prove something like "\bigvee_{x \in X} x = 1 \iff
% (\exists x \in X) [x = 1]" by induction.                     /Lars
%
\newcommand{\paritycomp}{\diamond}
\problem Suppose that $A$, $B$ and~$C$ are finite sets and that $R$~is
a relation on $A \times B$ and $S$~is a relation in $B \times C$. The
\emph{parity composition} of the relations $R$ and~$S$, denoted 
$S \paritycomp R$, is defined as follows:
\begin{displaymath}
  S \paritycomp R = \bigl\{
  (a,c) \in A \times C \suchthat
  \mbox{there is an odd number of~$b \in B$ such that
    $(a,b) \in R$ and $(b,c) \in S$}
  \bigr\}.
\end{displaymath}
Let $M_R$ and $M_S$ be the matrices representing $R$ and~$S$,
respectively. Find a formula for the entries in $M_{S \paritycomp R}$
and prove that this formula is correct.

\solution{%
  \textbf{Solution:} Suppose that $M_R = (r_{ab})$, $M_S = (s_{bc})$
  and $M_{S \paritycomp R} = (t_{ac})$. By the definition of matrix
  representation of relations,
  \begin{gather}
    r_{ab} = \begin{cases}
      1 & \mbox{if $(a,b) \in R$,} \\
      0 & \mbox{otherwise.}
    \end{cases} \\
    s_{bc} = \begin{cases}
      1 & \mbox{if $(b,c) \in R$,} \\
      0 & \mbox{otherwise.}
    \end{cases} \\
    t_{ac} = \begin{cases}
      1 & \mbox{if $(a,c) \in S \circ R$,} \\
      0 & \mbox{otherwise.}
    \end{cases}
  \end{gather}
  Now consider ``products'' of the form $r_{ab} \land s_{bc}$. Such a
  product is one iff $r_{ab} = 1$ and $s_{bc} = 1$, i.e., if $(a,b)
  \in R$ and $(b,c) \in S$. So, we want to set $t_{ac}$~to one iff
  there is an odd number of~$b$'s such that $r_{ab} \land s_{bc} = 1$.
  
  A good way to express this mathematically is to use the
  XOR operation, denoted by~$\bigoplus$.
  \begin{definition*}
    Let $S$~be a non-empty set of binary variables and let $s$~be a
    member of~$S$. Then
    \begin{displaymath}
      \bigoplus_{x \in S} x =
      s \oplus \biggl(\bigoplus_{x \in S-\{s\}} x\biggr).
    \end{displaymath}
    Furthermore,
    \begin{displaymath}
      \bigoplus_{x \in \emptyset} x = 0.
    \end{displaymath}
  \end{definition*}
  \begin{lemma*}
    Let $S$~be a set of binary variables. Then
    \begin{displaymath}
      \bigoplus_{x \in S} x = \begin{cases}
        1 & \mbox{if there is an odd number of ones in~$S$,} \\
        0 & \mbox{otherwise.}
      \end{cases}
    \end{displaymath}
  \end{lemma*}
  \begin{proof}
    The proof is by induction on~$|S|$. The base case is clear---when
    $S = \emptyset$, it contains no ones.
    
    Suppose that the claim is true for all sets~$S'$ of
    cardinality~$n$. We now prove that this implies that the claim is
    true for any~$S$ of cardinality $n+1$. We pick any $s \in S$ and
    let $S' = S-\{s\}$. By the definition of~$\bigoplus$,
    \begin{displaymath}
      \bigoplus_{x \in S} x =
      s \oplus \biggl(\bigoplus_{x \in S'} x\biggr).
    \end{displaymath}
    Since $|S'| = |S|-1 = n$, we can use the inductive hypothesis, 
    \begin{displaymath}
      \bigoplus_{x \in S'} x = \begin{cases}
        1 & \mbox{if there is an odd number of ones in~$S'$,} \\
        0 & \mbox{otherwise.}
      \end{cases}
    \end{displaymath}
    Let $t = \bigoplus_{x \in S'} x$. We get four cases
    \begin{displaymath}
      \begin{array}{cc|c}
        s & t & s \oplus t \\
        \hline
        0 & 0 & 0 \\
        0 & 1 & 1 \\
        1 & 0 & 1 \\
        1 & 1 & 0
      \end{array}
    \end{displaymath}
    Thus, the claim is true for any set of cardinality $n+1$.
  \end{proof}
  Using the symbol~$\bigoplus$ as defined above, we can put everything
  together and obtain the following theorem:
  \begin{theorem*}
    Suppose that $A$, $B$ and~$C$ are finite sets and that $R$~is a
    relation on $A \times B$ and $S$~is a relation in $B \times C$.
    Suppose that the matrix representations of $R$ and~$S$ are $M_R =
    (r_{ab})$ and $M_S = (s_{bc})$, respectively. Then $S \paritycomp
    R$ have the matrix representation $M_{S \paritycomp R} =
    (t_{ac})$, where
    \begin{displaymath}
      t_{ac} = \bigoplus_{b \in B} r_{ab} \land s_{bc}.
    \end{displaymath}
  \end{theorem*}
  \begin{proof}
    By the definition of parity composition,
    \begin{displaymath}
      t_{ac} = \begin{cases}
        1 & \mbox{if there is an odd number of~$b \in B$ such that
          $(a,b) \in R$ and $(b,c) \in S$} \\
        0 & \mbox{otherwise.}
      \end{cases}
    \end{displaymath}
    Using the matrix representation of $R$ and~$S$, respectively, we
    can rewrite this as
    \begin{displaymath}
      t_{ac} = \begin{cases}
        1 & \mbox{if there is an odd number of~$b \in B$ such that
          $r_{ab} \land s_{bc} = 1$} \\
        0 & \mbox{otherwise.}
      \end{cases}
    \end{displaymath}
    Now, this is exactly the same thing as saying that
    \begin{displaymath}
      t_{ac} = \bigoplus_{b \in B} r_{ab} \land s_{bc},    
    \end{displaymath}
    by the definition of~$\bigoplus$.
\end{proof}
}

% Spring 99 Pset 3
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\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.

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{problems}
\end{document}
