\documentstyle[12pt,twoside]{article}

\newcommand{\problem}{%
  \paragraph{Problem}}
\newcommand(\solution}{%
  \paragraph{Solution}}

\begin{document}


\begin{problems}

%BEGIN Kavita's problems
%END   Kavita's problems

%BEGIN Joe's problems
%END   Joe's problems

%BEGIN Ray's problems

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 5
\problem The famous Towers of Hanoi problem. There are three poles. On
one of the poles there is a stack of rings, largest at the bottom,
smallest at the top.  You have to move the rings from one pole
to another,
%pole $r$, $r \in \{1,2,3 \}$ to pole $s$, $s \in \{1,2,3 \}$
so that the rings are in the
same order on the new pole, while observing the following rules:
\begin{itemize}
\item
Only one ring may be moved at a time. 
\item At no time may a larger ring be on top of a smaller ring. 
\end{itemize}
Prove by induction that the Towers of Hanoi Problem can always be
solved.  


\noindent
{\bf Solution:}

\noindent
It is important to formalize the inductive hypothesis in the right way.
We are proving a predicate $P(n)=$``For any poles $P_1,P_2$, a Hanoi
tower of height $n$ can be moved from $P_1$ to $P_2$ according to
the rules above.'', for any $n\geq{1}$

\medskip
\noindent 
%
{\em Base case:} $P(1)$ is true because a single ring can be moved
from one pole to another in accordance with the rules.

\medskip
\noindent 
%
{\em Inductive case:} Let $n$ be some nonnegative integer.  Assume
$P(n)$.  We prove $P(n+1)$ as follows: Assume that a Hanoi tower $T$
of height $n+1$ has to be moved from pole $P_1$ to $P_2$.  Think about
the top $n$ rings of $T$ (all rings except the base ring $R$) as a
``subtower'' $T'$.  Since $T'$ is a Hanoi tower of height $n$, from
the inductive assumption $P(n)$, we know that we can move it according
to the Hanoi-Tower game rules from $P_1$ to $P_3$ (the ring $R$ on the
bottom of pole $P_1$ does not trouble us since it is bigger than all
rings of $T'$).  When such move of $T'$ from $P_1$ to $P_3$ is done,
we move $R$ from $P_1$ to $P_2$, and then we use the $P(n)$ assumption
again to argue that there are some Hanoi-Tower game moves which allow
$T'$ to be moved from $P_3$ to $P_2$, on top of $R$.  In this way, the
whole tower $T$ was moved from $P_1$ to $P_2$, and so $P(n+1)$ is
true.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 11
\problem 
Use induction to prove that if 
$A_1, A_2, \ldots A_n$ and 
$B_1, B_2, \ldots B_n$ are sets such that 
$A_k \subseteq B_k$ for all $k \in \{1,2,\ldots,n\}$
then 
$$
(A_1 \cap A_2 \cap \ldots \cap A_n)  \subseteq 
(B_1 \cap B_2 \cap \ldots \cap B_n). 
$$


\noindent
{\bf Solution:}

\noindent
Here the predicate is $P(n)=$``If $A_1, A_2, \ldots A_n$ and $B_1,
B_2, \ldots B_n$ are sets such that $A_k \subseteq B_k$ for all $k \in
\{1,2,\ldots,n\}$ then $ (A_1 \cap A_2 \cap \ldots \cap A_n) \subseteq (B_1
\cap B_2 \cap \ldots \cap B_n)$''.  We are proving it for $n\geq{1}$:

\medskip
\noindent 
%
{\em Base case:} $P(1)$ is true because it is the following tautology:
``If $A_1\subseteq B_1$ then $A_1\subseteq B_1$''.

\medskip
\noindent 
%
{\em Inductive case:} Let $n$ be some integer $n\geq{1}$.  Assume
$P(n)$.  Let's prove $P(n+1)$. Say we have two groups of $n+1$ sets
$A_1, A_2, \ldots A_{n+1}$ and $B_1, B_2, \ldots B_{n+1}$ s.t. $A_k
\subseteq B_k$ for all $k \in \{1,2,\ldots,n+1\}$.  Now we have to
show that
$$
(A_1 \cap A_2 \cap \ldots \cap A_{n+1}) \subseteq (B_1 \cap B_2 \cap \ldots
\cap B_{n+1}).
$$
Assume that $x\in(A_1 \cap A_2 \cap \ldots \cap A_{n+1})$.  Therefore
$x\in(A_1\cap A_2 \cap \ldots \cap A_{n})$ and $x\in{A_{n+1}}$.  By
inductive hypothesis $P(n)$, since $A_k \subseteq B_k$ for all $k \in
\{1,2,\ldots,n\}$, we have that $(A_1\cap A_2 \cap \ldots \cap
A_{n})\subseteq (B_1 \cap B_2 \cap \ldots \cap B_{n})$, and therefore
$x\in(B_1 \cap B_2 \cap \ldots \cap B_{n})$.  Since
$x\in{A_{n+1}}\subseteq{B_{n+1}}$ then $x\in(B_1 \cap B_2 \cap \ldots
\cap B_{n})\cap B_{n+1}= B_1 \cap B_2 \cap \ldots
\cap B_{n+1}$, which completes the proof of $P(n+1)$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 12
%\problem In Section 3.3 of the textbook there is a definition of
%strings and the concatenation operation on them.  For a string $w$ the
%notation $w^R$ is used to denote the reverse of string $w$. For
%example $1234^R$ is the string $4321$.  Prove by induction that for
%any concatenated strings $wv$, $(wv)^R=v^Rw^R$.

% Alternative 12
\problem In Section 3.3 of Rosen, there is a definition of
strings and the concatenation operation on them.  The
notation $w^R$ is used to denote the reverse of string $w$.  For
example $1234^R$ is the string $4321$.  
\begin{enumerate}
\item
Give a recursive definition of a reverse operation $w^R$ on strings.
\item
Prove by induction that for any concatenated strings $wv$,
$(wv)^R=v^Rw^R$.
\end{enumerate}


\noindent
{\bf Solution:}

\begin{enumerate}
\item
\noindent
The recursive definition of the reverse operation might look as
follows:
\begin{eqnarray*}
\lambda^R &=& \lambda\\
(wx)^R &=& x(w^R) \mbox{ \,\,\,\,if\,\,\, $w\in\Sigma^*$ and $x\in\Sigma$}
\end{eqnarray*}
The definition would be equivalent if the second line was $(xw)^R =
(w^R)x$.

\item
\noindent 
One way to prove it by induction is to prove the following predicate
$P(n)=$``For any $w,v\in\Sigma^*$, where $|v|=n$, $(wv)^R=v^Rw^R$'',
for $n\geq{0}$.

\noindent
{\em Base case:} $P(0)$ is true because if $|v|=0$ then $v=\lambda$,
and for every $w$, $(w\lambda)^R=w^R=\lambda{}w^R=\lambda^Rw^R$, where
the last equation follows from the base case of the recursive
definition of the reverse operation above.

\medskip
\noindent 
%
{\em Inductive case:} Pick $n\geq{0}$ and assume $P(n)$ is true.
Let's prove $P(n+1)$.  Pick $w,v\in\Sigma^*$ s.t. $|v|=n+1$.  By the
definition of length, it must be that $v=ux$ where $u\in\Sigma^*$ and
$x\in\Sigma$.  Furthermore, $|u|=n$.  Therefore, 
\begin{eqnarray*}
(wv)^R&=&(w(ux))^R
\\
&=&((wu)x)^R \mbox{ \,\,\,\,\, (because concatenation is associative)}
\\
&=&x(wu)^R \mbox{ \,\,\,\,\,\,\,\,\, (by the inductive definition
of reverse operation)}
\\
&=&x(u^Rw^R)\mbox{ \,\,\,\,\, (by the inductive assumption $P(n)$, since
$|u|=n$)}
\\
&=&(xu^R)w^R\mbox{ \,\,\,\,\, (again, by associativity of concatenation)}
\\
&=&(ux)^Rw^R\mbox{ \,\,\,\,\, (by the inductive definition
of reverse operation)}
\\
&=& v^Rw^R
\end{eqnarray*}
which proves $P(n+1)$.
\end{enumerate}


%END   Ray's problems

%BEGIN Ivan's problems (spring '98)
%END   Ivan's problems

%BEGIN George's problems
%END   George's problems

%BEGIN Josh's problems
%END   Josh's problems

%BEGIN Tina's problems

%Fall 99
%%%%%%%%%%%%%%%%%%%%%%%%%%
% Pset 2 problem 9
\problem \textbf{Structural Induction}

Suppose we start with a sequence of fully parenthesized arithmetic or
Scheme expressions, and then erase all the alphanumeric characters other
than parentheses.  The result is a string of parentheses which ``match
up''.

For example, erasing non-parenthesis characters from the expression
\texttt{(if (or x y) u v)} leaves the string \texttt{(())}.  Similarly,
erasing non-parentheses from the sequence of three arithmetic expressions
\[
\texttt{(x * x), (y + (3 * (z - 9))), ((x + y) * (u + w))}
\]
leaves the string
\[
\texttt{()((()))(()())}.
\]
On the other hand, even though the string \texttt{())(()} has an equal
number of left and right parentheses, it cannot be obtained by erasing in
this way---because the two middle parentheses don't match up.  Also, no
string of parentheses which begins with a right parenthesis or ends with a
left parenthesis can match up.

We can give an inductive definition of the set, SMU, of ``Strings which
Match Up'', as follows:

\begin{itemize}
\item The empty string (consisting of no parentheses) is an SMU.

\item If $s$ and $t$ are SMU's, then the string $\texttt{(}s\texttt{)}t$
is an SMU.  That is, the new string starts with a left parenthesis which
is followed by the parenthesis characters in the string $s$, followed by a
right parenthesis, followed by the parenthesis characters in the string
$t$.

\end{itemize}


There is a simple test to determine whether a string of parentheses is an
SMU: starting with zero, read the string from left to right adding one for
each left parenthesis and -1 for each right parenthesis.  A string
\emph{counts well} when the count never goes negative and is back to zero
by the end of the string.  Let CW be the set of strings of parentheses
which Count Well.

\bparts
\ppart Prove that CW contains SMU.

\solution{We prove by induction on the definition of SMU (that is,
structural induction) that every element of SMU counts well, so SMU is
contained in CW.  The induction hypothesis is
\[
P(s) ::\equiv s \in \mbox{CW}.
\]
\begin{proof}

{\bf Base Case}: $P(\mbox{empty string})$ holds since the count of the
empty string ends when it starts at zero.

{\bf Inductive Step:} Assume $P(s)$ and $P(t)$ are true.  We need to show
that $P(\texttt{(}s\texttt{)}t)$ is true.

The count values for $\texttt{(}s\texttt{)}t$ start with 0.  Reading the
initial left parenthesis yields 1 as the next count value.  This 1 serves
as the start of a series of count values exactly equal to the count values
of $s$, with each value incremented by one.  Since $s \in \mbox{CW}$ by
hypothesis, these incremented count values begin with 1, always stay
positive, and end with 1.  The right parenthesis immediately after $s$
reduces the ending count to 0.  This 0 serves as the start of the
remaining count values which are exactly the count values of $t$.  Since
$t \in \mbox{CW}$, these remaining values never go negative and end at 0.
Hence the entire sequence of count values for $\texttt{(}s\texttt{)}t$
starts with 0, never goes negative, and ends with 0, which proves that
$\texttt{(}s\texttt{)}t \in \mbox{CW}$.
\end{proof}}

\ppart Conversely, prove that SMU contains CW.

\solution{We show that every string $r\in \mbox{CW}$ is an SMU by
strong induction on the length of $r$.  The induction hypothesis is
\[Q(n) ::\equiv \forall r \in \mbox{CW}(\mbox{if $r$ is length $n$, then
$r \in \mbox{SMU}$}).\]
\begin{proof}

{\bf Base Case} $n = 0$: In this case there is only one string of length
$n$, namely the empty string, which is in SMU by definition, proving
$Q(0)$.

{\bf Inductive Step:} Assume that $Q(k)$ is true for all $k\leq n$, we
need to prove that $Q(n+1)$ is also true.

So suppose $r$ is a length $n+1$ string that counts well.  We must prove
that $r \in \mbox{SMU}$.

Now since $r$ counts well, it must start with a left parenthesis (or else
the count would immediately go negative).  Likewise, since the count for
$r$ returns to the value 0 by the end, $r$ must end with right
parenthesis.  So there must be a \emph{first} right parenthesis in $r$
after which the count returns to 0.  Let $s$ be the substring of $r$
between the initial left parenthesis and this right parenthesis.  So
\[
r = \texttt{(}s\texttt{)}t
\]
for some string $t$.

Since counts only change by one as each parenthesis character is read, and
the count for $r$ \emph{first} returns to 0 after the right parenthesis
following $s$, the count during $s$ must start and end with 1 and must
stay \emph{positive} in between.  But this implies that a count for $s$
alone, which would start with 0, would also end with 0 and stay
\emph{nonnegative} in between.  That is, $s$ by itself counts well.  Since
the length of $s \in \mbox{CW}$ is less than the length of $r$, we have by
strong induction that $s \in \mbox{SMU}$.

Further, we know the count for $r$ returns to 0 after the right
parenthesis following $s$, and since $r \in \mbox{CW}$, the count ends
with 0 again and stays nonnegative in between.  But this implies that $t$
counts well, and since the length of $t$ is less than the length of $r$,
we have by strong induction that $t \in \mbox{SMU}$.  Now by the second
case in the definition of SMU, we conclude $\texttt{(}s\texttt{)}t$,
namely $r$, is in SMU.
\end{proof}}

\eparts
%%%%%%%%%%%%%%%%%%%%%%%%%%
%END   Tina's problems


\end{problems}

\end{document}



