\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{\reading}[1]{}
  \newcommand{\omitsolution}[1]{#1}
  \usepackage[dark,first,bottom]{draftcopy}
  \draftcopyName{Solutions}{155}
\else 
  \typeout{}
  \typeout{Solutions *NOT INCLUDED*.} 
  \newcommand{\reading}[1]{#1\vfill\mbox{}\newpage}
  \newcommand{\omitsolution}[1]{\vspace*{1.0in}}
\fi
\typeout{}

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

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\tutref}{tut3}
\newcommand{\tutnum}{3}
\newcommand{\tutdate}{February 18, 2000}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

\begin{enumerate}
\item Write your name:

\bigskip

\item \textbf{Rosen 2.3, Ex. 35:} Show that if $n \mid m$, where $n$
  and $m$ are positive integers greater than 1, and if $a = b\
  (\text{mod } m)$, where $a$ and $b$ are integers, then $a = b\
  (\text{mod } n)$.

% we technically need a triple equals (congruent to) for each equals above.

\omitsolution{%
  \solution{Let $m = tn$.  Since $a = b\ (\text{mod } m)$ there exists
    an integer $s$ such that $a = b + sm$.  Hence $a = b + (st)n$, so
    that $a = b\ (\text{mod } n)$.
    }
  }

\vspace{2in}

\end{enumerate}

\newpage

\thispagestyle{empty}

\mbox{}

\setcounter{page}{0}

\newpage

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

%\begin{problems}

%%%%%%%%%% PROBLEM %%%%%%%%%

\problem 

Consider the following putative theorem and the accompanying proof.

\begin{theorem*}
  For any sets $A$, $B$, $C$, and $D$, if $A \times B \subseteq C
  \times D$ then $A \subseteq C$ and $B \subseteq D$.
\end{theorem*}

\begin{proof}
  Suppose $A \times B \subseteq C \times D$.  Let $a$ be an arbitrary
  element of $A$, $b$ be an arbitrary element of $B$, and $(a, b) \in
  A \times B$.  Since $A \times B \subseteq C \times D$, it follows
  that $(a, b) \in C \times D$.  Therefore, $a \in C$ and $b \in D$.
  Since $a$ and $b$ were arbitrary elements of $A$ and $B$,
  respectively, this shows that $A \subseteq C$ and $B \subseteq D$.
\end{proof}

Is the proof correct?  If so, what proof strategies does it use?  If
not, can it be fixed?  Is the theorem correct?

\omitsolution{%
  \solution{%
    The problem lies in the statement \emph{``let $a$ be an arbitrary
      element of $A$''} (and without loss of generality, $b$ an
    arbitrary element in $B$).  Namely, if $A = \emptyset$, $B = \{1,
    2, 3\}$, $C = \{1, 2\}$, and $D = \{3, 4\}$, then $A \times B
    \subseteq C \times D$ ($\emptyset \subseteq E$ for any set $E$),
    but $B \not\subseteq D$.  This is an example of the proof failing
    at a boundary case.%
    }%
  }

%%%%%%%%%% PROBLEM %%%%%%%%%

\newpage
\problem \textbf{Relations and Matrices} 

Let $A$ be the adjacency matrix for a digraph $G$ with $n$ vertices.  Note
that $A$ is a zero-one valued $n \times n$ matrix.  In this problem we use
the Boolean ``OR'' operation, $\vee$, instead of ``+'' when multiplying
zero-one valued matrices (this is called ``boolean'' matrix product).

%\begin{problemparts}

\problempart

For $k \in \naturals$, let $A^k$ be the $k$th {\em Boolean} power
of $A$.  Prove that ${A^k}_{ij} = 1$ iff there is a directed path of
length $k$ from the $i$th to the $j$th vertex of $G$.

\omitsolution{%
  \solution{%
    Let $P(n)$ be the predicate that ${A^n}_{ij} = 1$ iff there is a
    directed path of length $n$ from the $i$th to the $j$th vertex
    of $G$.  We prove that $P(n)$ holds for all $n\geq 1$ by induction
    on $n$.

    {\bf Inductive Hypothesis:} $P(k): {A^k}_{ij} = 1$ iff there is a
    directed path of length $k$ from the $i$th to the $j$th vertex
    of $G$.
 

    {\bf Base Case:} $k = 1$.  By the definition of an adjacent matrix
    A, $A_{ij} = 1$ iff there is a directed edge (directed path of
    length $k = 1$) from the $i$th to the $j$th vertex of $G$.
 

    {\bf Inductive Step:} Assume $P(k)$ to prove $P(k+1)$.
 
\[{A^k}_{ij} = \bigvee_{l \in G} ({A^k}_{il} \wedge A_{lj})\]

Now we consider both directions for the iff.

Case 1:

There is a directed path of length $k+1$ from the $i$th to the $j$th
vertex of $G$.  This path looks like $i, i_1, i_2, \dots i_k, j$.
Then consider $l = i_k$.  ${A^k}_{il} = 1$ (inductive hypothesis).
${A}_{lj} = 1$ (there is an edge from $i_k$ to $j$), under the Case 1
assumption.  Therefore,

\[({A^k}_{il} \wedge A_{lj}) = 1\]
\[{A^{k+1}}_{ij} = 1\]

Case 2: ${A^{k+1}}_{ij} = 1$.

Then $\exists\; l \in G : ({A^k}_{il} \wedge A_{lj}) = 1$.  Thus there
is an edge from $l$ to $j$ and there is path of length $k$ from $i$ to
$l$(by the inductive hypothesis) which looks like $i, i_1, i_2, \dots
i_{k-1}, l$.  Thus, there is a path of length $k+1$ from $i$ to $j$
which hits $l$ on the $k$th step and then has the $k+1$st edge from
$l$ to $j$.  This path follows the vertices: $i, i_1, i_2, \dots
i_{k-1}, l, j$.

Q.E.D.
}
}

\problempart

Let $B = A \vee I$ where $I$ is the $n \times n$ identity matrix.
Prove that ${B^k}_{ij} = 1$ iff there is a directed path of length
$\leq k$ from the $i$th to the $j$th vertex of $G$.

\omitsolution{%
  \solution{%
    From part a, it can be seen that ${B^k}_{ij} = 1$ iff there is a
    directed path of length $k$ from the $i$th to the $j$th vertex of
    $G'$, where $G'$ is the graph described by the adjacency matrix
    $B$.  Since $G'$ is just $G$ with self loops, a path exists
    between $i$ and $j$ in $G'$ iff a path exists between $i$ and $j$
    in $G$ (all vertices have paths of length $0$ to themselves).

    For any such path between $i$ and $j$ in $G'$, either it uses a
    self-loop edge or it does not.  If it does not, then the
    equivalent path in $G$ will have the same length.  If it does,
    then there is a shorter path in $G$ which can be obtained by not
    using the self loop.  So if there is a path of length $k$ between
    $i$ and $j$ in $G'$ then there is a path of length $\leq k$
    between $i$ and $j$ in $G$.

    If there is a path of length $\leq k$ between $i$ and $j$ in $G$,
    then it can be made to be of length $k$ by using self loops to
    lengthen the path.  Thus there is a path in $G'$ of length $k$ iff
    there is a path in $G$ of length $\leq k$.  Since ${B^k}_{ij} = 1$
    iff there is a path of length $k$ between $i$ and $j$ in $G'$ then
    ${B^k}_{ij} = 1$ iff there is a path of length $\leq k$ between
    $i$ and $j$ in $G$.%
    }%
  }

\problempart 

Conclude that ${B^n}_{ij} = 1$ iff there is a directed path from the $i$th
to the $j$th vertex.

\omitsolution{%
\solution
If ${B^n}_{ij} = 1$ then there is a directed path from the $i$th to
the $j$th vertex.  If ${B^n}_{ij} = 0$ then there is no path of length
$<=n$ from the $i$th to the $j$th vertex.  There must also be no path of
length $>n$ from the $i$th to the $j$th vertex.  If there were, then the
path must cross through some vertices twice, since the length of the path is
$>n$.  For those vertices through which the path passes twice, eliminate
the loops so that the path uses no vertex more than once.  This means the
path must be of length $<=n$, which reaches a contradiction, since we know
that there are no paths from $i$ to $j$ of length $<=n$.  Therefore, if
${B^n}_{ij} = 0$ there is no path from $i$ to $j$ at all.\\
}

%%%%%%%%%% PROBLEM %%%%%%%%%

\newpage
\problem \textbf{Topological Sort of a DAG}

Consider the following definitions of a \emph{cycle} and of a
\emph{directed acyclic graph (DAG)}.

\begin{definition*}
  A \textbf{cycle} is a walk that ends where it started (i.e., the
  last vertex equals the first).
\end{definition*}

\begin{definition*}
  A \textbf{directed acyclic graph (DAG)} is a directed graph with no
  cycles.
\end{definition*}

As an example, Figure~\ref{fig:dag-one} contains a picture of a directed
acyclic graph.

\begin{figure}[htbp]
  \centerline{\psfig{figure=figures/dag.eps,height=2.0in}}
  
  \caption{This is a picture of a directed acyclic graph.  Vertices
    are labeled with course numbers.  An edge from $u$ to $v$
    indicates that course $u$ is a prerequisite for course $v$.}

  \label{fig:dag-one}
\end{figure}

Now, consider the following definition of a topological sort of the
vertices of a DAG $G$.

\begin{definition*}
  A \textbf{topological sort} of the vertices of a DAG $G$ is a
  sequence comprised of all the vertices of $G$ (each appearing once),
  such that for any two vertices $u$ and $v$ of $G$, if $u$ appears
  before $v$, then there is no edge from $v$ to $u$.
\end{definition*}

We want you to prove the following theorem.

\begin{theorem*}
  Every DAG has a topological sort.
\end{theorem*}

The trick that you need to use is that it is possible to pick a
``first'' vertex for your topological sort and then proceed
inductively.  

\bigskip
\hrule

\problempart %
Consider the following definition of a minimal vertex of a DAG.
Notice that there can be more than one minimal vertex.

\begin{definition*}
  A \textbf{minimal} vertex $u$ in a DAG $G$ is a vertex for which
  there does not exist another vertex $v$ in $G$ such that the edge
  from $v$ to $u$ is in $G$.
\end{definition*}

What is the minimal vertex of the DAG in Figure~\ref{fig:dag-one}?

\omitsolution{%
  \solution{%
    18.01, 8.01, 6.001, and 6.170 are all minimal vertices.
    }%
  }

\problempart %
In fact, every DAG has a minimal vertex.  Prove the following lemma.

\begin{lemma*}
  Every DAG has a minimal vertex.
\end{lemma*}

\omitsolution{%
  \begin{proof}
    We prove that every DAG $G$ has a minimal vertex by contradiction.
    Consider a DAG $G$ with $n$ vertices.  Suppose that no vertex of
    $G$ is minimal.  Then, for every vertex of the graph there exists
    another vertex that points to it.  Now, take some vertex $v \in G$
    and define the following walk in $G$ recursively: $v_0=v$, and for
    $i > 0$, $v_i$ is some vertex that points to the vertex $v_{i-1}$.

    This definition is a bit odd because it is nondeterministic.  But
    it doesn't matter which preceding vertex you pick at each step.
    The key is that it defines some $v_i$ for every $i$.

    Now note that the sequence of vertices $v_{n+1},\ldots,v_0$ is a
    walk of length $n+1$; call this walk $w$.  Since the DAG $G$ has
    only $n$ vertices, it follows that some vertex is repeated along
    the walk $w$; that is, it is the case that $v_i=v_j$, for some $i
    < j$.  But this means that $v_i,\ldots,v_j$ is a cycle, which is
    impossible in a DAG; thus, a contradiction.%
  \end{proof}
  }

\problempart %
Give an example of a topological sort of the vertices of the DAG in
Figure~\ref{fig:dag-one}.
  
\omitsolution{%
  \solution{%
    }%
  }

\problempart %
Use the above lemma to prove the existence of a topological sort for
every DAG.

\omitsolution{%
  \solution{%
    By (ordinary) induction. \\ $P(n)$ = any DAG $G$ with $n$ vertices
    has a topological sort.

    Base case $(P(1))$: for a DAG with one vertex, the one vertex
    makes a topological sort. \\ 

    Inductive step: Assume $(P(n))$. Consider a DAG $G'$ of $n+1$
    vertices and a DAG $G$ of $n$ vertices that results from removing
    an arbitrary minimal vertex of $G'$; call it $u$.  Recall that by
    our lemma any DAG has a minimal vertex.  We must also argue that
    what we are left is also a DAG.

    By the inductive hypothesis, the DAG $G$ has a topological sort.
    Thus, a topological sort for $G'$ is $u$ followed by all the other
    vertices in $G$ ordered according to the topological sort of $G$.

    Thus, we have shown by induction that every DAG has a topological
    sort.%
    }%
  }

%%%%%%%%%% PROBLEM %%%%%%%%%

\newpage
\problem \textbf{Scheduling Courses}
% source: fall98/tutorials/H19-rec4.tex, beginning

We consider a simple kind of scheduling problem --- for MIT courses with
prerequisites.  The problem is to determine how a student could complete
all of the courses in the fewest terms, under the simplifying, if
unlikely, assumption that there is no limit on the number of courses a
student can take in a term as long as their prerequisites have all been
met.  We model this problem with a digraph.  An example is shown in
Figure~\ref{fig:dag}.

\begin{figure}[htbp]
  \centerline{\psfig{figure=figures/dag.eps,height=2.0in}}

  \caption{This is a picture of a directed acyclic graph.  Vertices
    are labeled with course numbers.  An edge from $u$ to $v$
    indicates that course $u$ is a prerequisite for course $v$.}

  \label{fig:dag}
\end{figure}

This example is a DAG.  Of course it is possible that the faculty in
charge of courses created a cycle of prerequisites; this would mean
that it was impossible to fulfill the prerequisites of any of the
courses in the cycle before taking the course.  Presumably this would
not be the intention of the faculty, so we assume that whatever the
prerequisite requirements may be, they do not have cycles; so the
digraph corresponding to the prerequisites will always be a DAG.

The connectedness relation of a DAG is a {\em partial order}.  The
example in Figure~\ref{fig:dag} suggests the reason for this name.
The edges in this graph restrict the order in which a student may take
classes.  For example, 6.001 must be taken before 6.003.  Of course,
the student still has some choice about the order; for this reason,
the set of classes is said to be ``partially'' ordered by this system
of prerequisites.  If we write $u \succeq v$ to mean that $u=v$ or
there is a directed path from vertex $u$ to $v$, then the relation
$\succeq$ is obviously \emph{transitive}:
\[ [u \succeq v \wedge v \succeq w] \implies u \succeq w,\]
and \emph{antisymmetric}:
\[ [u \succeq v \wedge v \succeq u] \implies u = v.\]
Formally, a partial order on a set is just a binary relation which is
transitive and antisymmetric.

Two elements $u$ and $v$ are said to be {\em comparable} under a
partial order, $\succeq$, iff $u \succeq v \vee v \succeq u$.  When
the partial order is the one from the connectedness relation of a DAG,
vertices $u,v$ are comparable precisely when $u=v$ or there is a
directed path from $u$ to $v$ or vice-versa.  Otherwise, $u$ and $v$
are incomparable.  For example, 18.01 and 6.002 are comparable since
there is a directed path from 18.01 to 6.002.  However, 18.01 and 8.01
are incomparable because there is no directed path from one to the
other.

\problempart  How many terms are necessary to complete all of the
courses in Figure~\ref{fig:dag}, assuming prerequisites are observed,
but course load is no issue?

\omitsolution{%
\solution
The answer is suggested by the way Figure~\ref{fig:dag} is drawn.
Each term the student could take all the courses in a horizontal row,
starting with the first row and working down.  All of the courses in
each row are incomparable, and all the necessary prerequisites are in
previous rows.  Since there are six rows, the student can finish in
six terms.

Furthermore, there is no way to finish in fewer than six terms, since each
term the student can take at most one course in the six-course sequence
18.01, 18.03, 6.002, 6.004, 6.033, 6.857.  Notice that this sequence
constitutes the longest directed path in the graph.
}

\problempart Explain why every (finite) DAG has a finite longest walk.

\omitsolution{%
\solution If path was as long as number of vertices, $V$, a vertex
would repeat and this would be a cycle.  So the length of a path is at
most $\card{V}-1$.  So the set 
\[\set{\card{V} - (k+1) : k \mbox{ is the length of a path in the DAG}}\]
is a nonempty set of natural numbers, and by the Well-ordering Principle, it has a
least element $k_{min}$.  Then $\card{V}-k_{min}$ is nonempty the
length of the longest path.  QUIBBLE: why is the set nonempty?  Actually
it might be empty if the graph has no edges; to cover this case we should
regard a single vertex as a path of length 0.
}

\medskip

% A {\em chain} in a partial order, $\succeq$, is a single element or a
% nondecreasing sequence of elements.  That is, $a_1, a_2, \ldots, a_n$ is a
% chain providing $a_{i+1} \succeq a_i$ for all $1 \leq i < n$.  So every
% path in a DAG is a chain in the partial order determined by connectedness
% in the DAG.  An \emph{antichain} is a set of elements no two of which are
% comparable.  In a DAG, an antichain is a set of vertices with no paths
% connecting any two of them.  Any antichain in the course prerequisite DAG
% identifies a set of courses that can be taken in any order, or
% simultaneously, as long as their other prerequisites have been met.
 
We let $t$ be the number of vertices in the longest walk in the graph.
% This chain must be a path (Exercise: Why?).  
Now at least $t$ terms are
necessary to complete all the courses, because at most one course on the
chain can be taken each term.

\problempart Show that every DAG with a critical path of length $t$
has a schedule with $t$ steps.

\omitsolution{%
  \solution{%
    \begin{theorem*}
      If the longest path in a DAG $G$ has length $t-1$, then the
      vertices can be partitioned into a sequence of $t$ blocks such
      that any edge into a vertex must start at a vertex from an
      earlier block.
    \end{theorem*}

    \begin{proof}
    \end{proof}
    }%
  }

\problempart Show that there is a schedule for taking courses
which achieves the minimum number of terms, $t$.  

\omitsolution{%
  \solution{%
    The solution to the previous part implies that $t$ terms are
    sufficient.  In term $i$, the student should take the set of
    courses in the $i$th block.  Since the edges into any block come
    from an earlier block, all the prerequisites of courses in a block
    have been taken by the time the block is scheduled to be taken.
    And since the blocks partition the set of all courses, the student
    will complete every course.
    }%
  }

\end{document}

\endinput

\footnote{Rosen also requires that a partial
order be \emph{reflexive}: $v \succeq v$ for all $v$.  In 6.042 we will
not always insist on reflexivity, so the relation ``there is a directed
path of \emph{positive} length from vertex $u$ to $v$,'' will also count
as a partial order.  But above we have defined the connectedness relation
of a DAG so it is in fact reflexive.}.

%%%%%%%%%% PROBLEM %%%%%%%%%

\problem \textbf{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.

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

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


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

\omitsolution{%
\solution{%
  \setcounter{problempart}{0}
  \problempart
  \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}

  \problempart
  \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}

  \problempart

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

%%%%%%%%%% PROBLEM %%%%%%%%%

\problem \textbf{False Proof: } 

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

\omitsolution{%
  \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 %%%%%%%%%

% kdmclookhere %
  \problem \textbf{Ackermann's function} p. 211 definition, Rosen 3.3, problem
        39, followed by an inductive proof, say ex. 41 (double-induction), 42.

\omitsolution{%
  \begin{solution}
    \emph{not done yet}
  \end{solution}
}

%%%%%%%%%% PROBLEM %%%%%%%%%
  \problem \textbf{Recursively Defined Sequences}

% Variant of problem on practice quiz Fall98.

Consider a function $f$ from natural numbers to rational numbers,
defined so that it has the following properties:

\begin{enumerate}
\item $f(0) = 65$, and $f(1) = 26$,
\item for all $n > 2$, either
   \begin{enumerate}
    \item $f(n)$ is the sum of two numbers earlier in the sequence, or
    \item $f(n)$ is obtained by dividing the product of any $k>0$ numbers
          of the form $f(i)$, $i < n$, by $13^{k-1}$.
   \end{enumerate}
\end{enumerate}
Prove that every function value is a natural number divisible by $13$.

\omitsolution{%
  \begin{solution}
    \emph{again, focuses on divisibility.  too easy???}
  \end{solution}
} 

%%%%%%%%%% PROBLEM %%%%%%%%%

\problem Let $R$ be any relation.  Prove that any relation that
contains $R$ is reflexive (resp. symmetric, transitive) contains the
reflexive (resp. symmetric, transitive) closure of $R$.   This means
the closure is the "smallest" containing set that has the property.

\omitsolution{%
  \begin{solution}
    \emph{not done yet}
  \end{solution}
}

%%%%%%%%%% PROBLEM %%%%%%%%%

\problem  We define a well-balanced string of parentheses to be:

\begin{itemize}

\item The empty string, $\lambda$.

\item The string (V)W, where V and W are well-balanced strings of
parentheses.

\end{itemize}

The following procedure is designed to take an input that is a string
consisting only of left and right parentheses.
If its input is a well-balanced string of parentheses, it is meant
to return $\lambda$.
If its input is a string of the form P)W, where P is a
well-balanced string of parentheses and W is an arbitrary
(possibly empty) string, then it is meant to return the string )W.
For any other input, it is meant to return the special value {\em error}.
It uses the auxiliary procedures First-char and Remove-first-char, which
return the first character of a string and everything but the first character
of a string, respectively.  (The strings are presumed to be non-empty in
both cases).

\begin{tabbing}

Check($w$) \\
\ \ \ \= if ($w = \lambda$) return($\lambda$) \\
      \> if (First-char($w$) = ``(") \\
      \> \ \ \ \= $w \leftarrow \mbox{Check(Remove-first-char}(w))$ \\
      \>       \> if (($w = \lambda$) or ($w = ${\em \ error})) \\
      \>       \> \ \ \ \= return({\em error}) \\
      \>       \> else \\
      \>       \>       \> $w \leftarrow \mbox{Check(Remove-first-char}(w))$ \\
      \> return($w$) \\
\\
\end{tabbing}

Is the procedure correct?  Either prove correctness or provide a
counterexample.  You should only consider inputs which consist entirely
of left and right parentheses.

\omitsolution{%
\begin{solution}
\emph{not done yet.}
\end{solution}
}
