\documentclass[12pt,twoside]{article}

\usepackage{psfig}

\input{macros-course}
\def\cent{{\not\!\mathrm{c}}}

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

\typein[\answer]{Include solutions? (y/n) }
\def\yes{y}
\ifx\answer\yes
  \typeout{}
  \typeout{Solutions *INCLUDED*.} 
  \newcommand{\solution}[1]{\bigskip \textbf{Solution:}\\ #1\bigskip\newpage}
  \usepackage[dark,first,bottom]{draftcopy}
  \draftcopyName{Solutions}{155}
\else 
  \typeout{}
  \typeout{Solutions *NOT INCLUDED*.} 
  \newcommand{\solution}[1]{\vfill\mbox{}\newpage}
%  \newcommand{\solution}[1]{}
\fi
\typeout{}

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

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\tutref}{tut2}
\newcommand{\tutnum}{2}
\newcommand{\tutdate}{February 11, 2000}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\handout{\tutref}{Mini-Quiz \tutnum}{\tutdate}

\begin{enumerate}
\item Write your name:

\bigskip

\item (Rosen, Sec. 1.5, Ex. 21) Let $A$ and $B$ be subsets of a
  universal set $U$.  Show that $A \subseteq B$ if and only if
  $\overline{B} \subseteq \overline{A}$.

\vspace{2in}

\item (Rosen, Sec. 1.6, Ex. 15) Determine whether each of the
  following functions is a bijection from $\reals$ to $\reals$.
%
\begin{enumerate}\itemsep 0\baselineskip
\item $f(x) = 2 x + 1$
\item $f(x) = x^2 + 1$
\item $f(x) = x^3$
\item $f(x) = (x^2 + 1)/(x^2 + 2)$
\end{enumerate}

\vspace{2in}

\end{enumerate}

\newpage

\thispagestyle{empty}

\mbox{}

\setcounter{page}{0}

\newpage

\handout{\tutref}{Tutorial \tutnum~Problems}{\tutdate}

\begin{problems}

  \problem \mbox{} \\ 

  \vspace*{-\baselineskip}

  \begin{claim*}
    If every vertex in a graph is adjacent to another vertex, then the
    graph is connected.
  \end{claim*}
  
  \begin{proof}
    The proof is by induction on the number of vertices, $n$,
    comprising the graph.  Let $P(n)$ be the predicate: ``If every
    vertex in an $n$-vertex graph is adjacent to another vertex, then
    the graph is connected''.  In the base case, $P(1)$ is trivially
    true because there is only one vertex.

    In the inductive step, we assume $P(n)$ to prove $P(n+1)$.  Start
    with an $n+1$-vertex graph, $G'$, in which every vertex is
    adjacent to another vertex.  Let $e$ be any edge in $G'$
    connecting two vertices $v$ and $u$.  Moreover, let $G$ be the
    graph obtained from $G'$ by removing the vertex $v$ and all edges
    incident on $v$; namely, $G$ has $n$ vertices.

%\begin{figure}[htbp]
%%
%\centerline{\psfig{figure=false.eps,height=1.5in}}
%%
%\caption{This picture depicts two situations.  In one, vertices $x_1$
%  and $x_2$ both are among the vertices of $G$, and so there is a
%  connecting path by induction.  In the second, $v = x_1$ and $x_2$ is
%  a vertex of $G$.  In this case there is a connecting path because
%  there is an edge from $v$ to $u$ and a path in $G$ from $u$ to $x_2$
%  by induction.}% 
%\label{fig:false}
%\end{figure}

    To complete the proof, we must show that for every pair of
    distinct vertices $x_1$ and $x_2$ in $G'$, there is a path between
    them.  If both $x_1$ and $x_2$ are vertices of $G$, since $G$ has
    $n$ vertices, the fact that $x_1$ and $x_2$ are connected follows
    from our inductive hypothesis.  Thus, there is a path between
    $x_1$ and $x_2$ in the $n+1$-vertex graph $G'$.  Otherwise, one of
    the vertices is $v$ and the other is in $G$.  Without loss of
    generaliry, let $x_1 = v$ and $x_2$ be in $G$.  By the induction
    hypothesis, we know that $x_2$ is connected to $u$.  Thus, since
    $v$ and $u$ are connected through the edge $e$, there is a path
    from $x_1=v$ to $x_2$ through vertex $u$.
\end{proof}

\solution{%
  The error is in the statement ``\emph{since $G$ has $n$ vertices,
    the fact that $x_1$ and $x_2$ are connected follows from our
    inductive hypothesis.}'' The induction hypothesis does not say
  that every $n$-vertex graph is connected, but only ``\emph{If every
    vertex in an $n$-vertex graph is adjacent to another vertex, then
    the graph is connected}''.  For example, if $G'$ is the graph with
  vertices 1, 2, 3, 4 and edges $\set{1,2}$ and $\set{3,4}$, then
  removing vertex 1 to form $G$ leaves vertex 2 without an adjacent
  vertex in $G$, and we can't conclude by the induction hypothesis
  that $G$ is connected (which of course it isn't).

  The problem is a common source of mistakes in inductive proofs.  The
  error occurs when the induction hypothesis $P(n)$ is itself an
  implication of the form $A(n) \Rightarrow B(n)$.  In this instance,
  $A(n)$ is the statement ``every vertex in an $n$-vertex graph is
  adjacent to another vertex'' and $B(n)$ is the statement ``the graph
  is connected''.

  In the inductive step of a correct proof, we assume $A(n)
  \Rightarrow B(n)$ in order to prove $A(n+1) \Rightarrow B(n+1)$.  In
  an erroneous proof, we assume $B(n)$ in order to prove $A(n+1)
  \Rightarrow B(n+1)$.  This is precisely what happened; we assumed
  ``the graph is connected'' rather than ``If every vertex in an
  $n$-vertex graph is adjacent to another vertex, then the graph is
  connected''.  }

  \problem \mbox{} \\ 

  \vspace*{-\baselineskip}

  \begin{claim*}
    If every vertex in a graph is adjacent to another vertex, then the
    graph is connected.
  \end{claim*}
  
  \begin{proof}
    The proof is by induction.  Let $P(n)$ be the predicate: ``If
    every vertex in an $n$-vertex graph is adjacent to another vertex,
    then the graph is connected''.  In the base case, $P(1)$ is
    trivially true because there is only one vertex.

    In the inductive step, we assume $P(n)$ to prove $P(n+1)$.  Start
    with an $n$-vertex graph $G$; this is connected by the induction
    hypothesis.  Now add a vertex $v$ to construct an $n+1$-vertex
    graph $G'$.  By assumption $v$ is connected to one of the vertices
    of $G$; call this particular vertex $u$.

    Now we must show that for every pair of distinct vertices $x_1$
    and $x_2$, there is a path between them.  If both $x_1$ and $x_2$
    are among the vertices of $G$, then there is a path between them
    by the induction hypothesis.  Otherwise, one of the vertices is
    $v$ (say $x_1$) and the other (say $x_2$) is among the vertices of
    $G'$.  These are connected by the path from $x_1$ to $u$ to $x_2$.
  \end{proof}

  \solution{%
    The error is in the early statement ``Start with an $n$-vertex
    graph; this is connected by induction.''  The induction hypothesis
    does not say that every $n$-vertex graph is connected, but only,
    ``{\em if every vertex in an $n$-vertex graph is adjacent to
      another vertex,} then the graph is connected''.

    The core problem here is called \emph{buildup error} and is a
    common source of mistakes in inductive proofs.

    Buildup error occurs when the induction hypothesis $P(n)$ is
    itself an implication of the form $A(n) \Rightarrow B(n)$.  In
    this instance, $A(n)$ is the statement, ``every vertex in an
    $n$-vertex graph is adjacent to another vertex'' and $B(n)$ is the
    statement, ``the graph is connected''.

    In the inductive step of a correct proof, we assume $A(n)
    \Rightarrow B(n)$ in order to prove $A(n+1) \Rightarrow B(n+1)$.
    In an erroneous proof, we assume $B(n)$ in order to prove $A(n+1)
    \Rightarrow B(n+1)$.  This is precisely what happened; we assumed,
    ``the graph is connected'' rather than, ``if every vertex in an
    $n$-vertex graph is adjacent to another vertex, then the graph is
    connected''.  }
  
\problem  \mbox{} \\
% false induction
% spring 00, Victor Luchangco

\vspace*{-\baselineskip}

\begin{claim*}
  For $n \in \nats, n\geq 1$, any $2n \times 2n$ square grid can be
  tiled by L-shaped tiles such that any particular square is left
  untiled.
\end{claim*}

\begin{proof}
  The proof is by strong induction on $n$.  Let $P(n)$ be the
  predicate: ``Any $2n \times 2n$ square grid can be tiled by L-shaped
  tiles such that any particular square is left untiled''.
  \begin{description}\itemsep 0\baselineskip
  \item[Base Case:] \mbox{} \\ %
    The base case, for $n = 1$, is very simple, just use one tile.
  \item[Inductive Step:] \mbox{} \\ %
    Assume that this is true for all square grids smaller than $2n$,
    and we prove it for the $2n \times 2n$ square grid.  This follows
    the proof of the $2^n \times 2^n$ case: Given a $2n \times 2n$
    square grid, with one square designated to be left untiled, we
    construct a tiling (using L-shaped tiles) for all the other
    squares, as follows: Divide the square grid up into four
    quadrants, each $n \times n$.  By the inductive hypothesis (since
    $n < 2n$ for all $n >= 1$), we can tile each of these quadrants
    (with the L-shaped tiles) completely, except for one square of our
    choice.  For the quadrant with the square to be left untiled,
    choose that square.  For the others, choose the squares at the
    corner where the quadrants meet.  This forms an L-shaped space at
    the center of the $2n \times 2n$ square grid, which can be filled
    by a single L-shaped tile.  Thus, the entire $2n \times 2n$ square
    grid is tiled, except for the square designated.
  \end{description}
\end{proof}

Point out any logical errors in this proof (that is, not simply places
where some steps were skipped, but where there is actually an error,
though you are free to point out places where more steps should have
been included for clarity).  Then, either construct a correct proof,
or show that the claim is false.

\solution{%
  }

\problem
% strong induction
% source: Velleman section 6.4, problem 5

Let $F_n$ be the $n^{\text{th}}$ Fibonacci number, for all $n \in
\mathbb{N}$.  Recall that the Fibonacci numbers are defined
recursively as follows: $F_0 = 0$, $F_1 = 1$, and $F_n = F_{n-1} +
F_{n-2}$, for all $n \in \mathbb{N}, n \geq 2$.

(a) Prove that for all $n \in \mathbb{N}$, $\sum_{i = 0}^{n} F_i =
F_{n + 2} - 1$.

(b) Find a formula for $\sum_{i = 0}^{n} F_{2 i}$ and prove that the
formula is correct.

\solution{%
  }

\problem
% structural induction

Consider the recursive definition of the set $F$ of full binary trees:
%
\begin{enumerate}\itemsep 0\baselineskip
\item A single node is in $F$.

\item If $t$ and $t'$ are in $F$, then the structure formed from $t$,
  $t'$, and a single new node, with an arrow labelled ``left'' from
  the new node to $t$ and another arrow labelled ``right'' from the
  new node to $t'$, is also in $F$.
\end{enumerate}

The recursive definition of the set $F$ of full binary trees is
similar to the one for binary trees, except that we only allow the
recursive definition step that includes both a left and a right child.

(a) Give the structural inductive definition of the set $F$.

(b) Define the function $\ms{numleaves}(t)$, for $t \in F$, giving the
number of ``leaves'' of the full binary tree $t$; that is,
$\ms{numleaves}(t)$, for $t \in F$, gives the number of nodes in $t$
that do not have children.  Your definition should be recursive, based
on the recursive definition of the set $F$.

(c) Define the function $\ms{numinternal}(t)$, for $t \in F$, giving
the number of ``internal'' nodes of the full binary tree $t$; that is,
$\ms{numinternal}(t)$, for $t \in F$, gives the number of nodes in $t$
that do have children.  Your definition should be recursive, based on
the recursive definition of the set $F$.

(d) Prove by structural induction that for any full binary tree $t$ in
$F$, $\ms{numleaves}(t) = 1 + \ms{numinternal}(t)$.

\solution{%
  }

\problem

\emph{The Towers of Hanoi.}

There are three poles.  On the first pole there is a stack of rings of
increasing size, with the smallest ring on top of the stack.  The
second and third poles are empty.  The challenge is to move the entire
stack of rings to the second pole, while obeying the following rules:
\begin{itemize}
\item ~~Rings may only be moved one at a time from one pole to another.
\item ~~A ring may only be moved if it is on the top of a stack.
\item ~~A ring may only be placed on top of a larger ring.
\end{itemize}

Suppose there are $n\ge 1$ rings initially stacked on the first pole
and rings are only moved according to these rules.

\bparts

\ppart Prove that no matter how many moves are made, the rings stacked
on each pole, if any, increase in size from the top.

\ppart Prove that there is a way to move all the rings to the second
pole in $2^n-1$ moves.


\ppart Prove that the number of moves necessary to move all $n$ rings
from the first pole to the second is \emph{at least} $2^n-1$.

\eparts

\solution{%
  \bparts \ppart
  \begin{proof}
    The proof is by induction on the number of moves~---~not the
    number of rings.

    Let $P(k)$ be the predicate: ``After $k$ moves, the rings stacked
    on each pole increase in size from the top.''  The base case
    $P(0)$ follows because initially, that is, after zero moves, the
    rings are in increasing order.

    Now assume $P(k)$, namely, that they are in order on every pole
    after $k$ steps.  Suppose on the $k+1$st move ring $R$ is moved
    from pole $i$ to pole $j\neq i$.  Then the rings left on pole $i$,
    if any, are still in order.  Also, the ring that was on top of
    pole $j$, if any, must be larger than $R$ according to the rules,
    so the rings on pole $j$ increase in size starting from ring $R$
    on top.  Of course the rings on the remaining pole, if any, are
    unchanged, and so remain in increasing order.  Hence all poles
    have rings in increasing order from the top after $k+1$ moves,
    that is, $P(k+1)$ holds.
  \end{proof}

  \ppart
  \begin{proof}
    The proof is by induction on the number of rings $n$.  However, in
    order to simplify the proof, we strengthen the induction
    predicate.  In particular, we allow there to be $n$ \emph{or more}
    rings initially stacked in increasing order on \emph{any} given
    pole~---~not necessarily the ``first'' pole.

    Let $P(n)$ be the predicate: ``For $i \in \set{1,2,3}$, suppose
    there are $n \geq 1$ or more rings stacked on pole $i$ in
    increasing order from the top.  Suppose also that the rings, if
    any, on top of the other two poles are larger than the top $n$
    rings stacked on pole $i$.  Then, the top $n$ rings stacked on
    pole $i$ can be moved to any other pole in $2^n-1$ legal steps.''

    Notice that it follows as a special case of $P(n)$, that $n$ rings
    stacked in order on pole 1 can be moved to pole 2 in $2^n-1$ legal
    steps, as required.

    Now we prove $P(n)$ by induction on the number of rings $n$.
    Without loss of generality, let $i$ denote the pole on which the
    $n$ rings are stacked initially, $j$ denote the pole on which we
    must move the $n$ rings initially stacked on pole $i$, and $k$
    denote the remaining pole.
    \begin{description}\itemsep 0ex
    \item[Base Case:] \mbox{} \\ %
      $P(1)$ is true if the ring on top of pole $j$, if any, is larger
      than the ring on pole $i$, then the single ring on pole $i$ can
      be moved in $2^1-1 =1$ legal step onto pole $j$.
    \item[Inductive Step:] \mbox{} \\ %
      Assume $P(n)$ holds for some integer $n \ge 1$.
      
      Now, we must prove that $P(n+1)$ holds.  We assume that there
      are $n+1$ rings stacked in increasing order on pole $i$ and that
      the rings on the other two poles are larger than the top $n+1$
      rings stacked on pole $i$.  By the induction hypothesis, we can
      move the top $n$ rings from pole $i$ to pole $k$ in $2^n-1$
      moves.  Subsequently, it is legal to move the top ring on pole
      $i$, which is the $n+1$th ring initially stacked on pole $i$,
      from pole $i$ to pole $j$.  Finally, by the induction hypothesis
      we can move the top $n$ rings stacked on pole $k$ to pole $j$ in
      $2^n-1$ more steps.  Concluding, we have succeeded to move the
      top $n+1$ rings from pole $i$ to pole $j$ in a total of $(2^n-1)
      + 1 + (2^n-1) = 2^{n+1}-1$ legal moves; that is, we have shown
      that $P(n+1)$ is true.
  \end{description}
  \end{proof}

  \ppart
  \begin{proof}
    The solution to this part is similar to the solution to part (b).
    The key is in realizing that when the $n+1$st largest ring on pole
    $i$ is first moved to pole $j$, the $n$ rings stacked initially on
    top of pole $i$ must, by part~(a), appear in increasing order on
    pole $k$.  Thus, by the induction hypothesis at least $2^n-1$
    moves must have occurred already.  Similarly, at least another
    $2^n-1$ moves are needed after the $n+1$st ring is placed on pole
    $j$ in order to move the $n$ rings from pole $k$ to pole $j$.
  \end{proof}
  \eparts }

\end{problems}

\end{document}
