\documentclass[11pt,twoside]{article}
\usepackage{amsmath}
\input{macros-course}

\newtheorem{mytheorem}{Theorem}
\newtheorem{myfalsetheorem}[mytheorem]{False Theorem}

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

\begin{document}

\tutprobn{3}{Friday, 9/17/99}{September 15, 1999}

\begin{problems}

\problem Use induction to show every number of dollars exceeding
\$141 can be formed using bills of denominations \$11 and \$13.
\hint $11\cdot 6 + 13\cdot (-5)=1$.

\solution{Note that
\begin{eqnarray*}
1 & = & 11\cdot 6 + 13\cdot (-5)\\
& = & 11\cdot 6 + 11\cdot (-13) + 13\cdot (-5) + 13 \cdot 11\\
& = & 11\cdot (-7)+13\cdot 6.
\end{eqnarray*}

The induction hypothesis $P(n)$ will be: ``$n$ can be represented as
$11\cdot x+13\cdot y$ for some nonnegative $x,y \in \naturals$.''  Notice
that $P(n)$ implies that change for $n$ can be given with $x$ \$11 bills
and $y$ \$13 bills.

\begin{proof}
{\em Base case:} $P(142)$ is true because $142=11 \cdot 7 + 13 \cdot 5$.

{\em Inductive case:} Let $n$ be some integer $\geq 142$.  Assume $P(n)$,
i.e. that $n=11\cdot x+13\cdot y$ where $x,y \geq 0$.

To prove $P(n+1)$, we consider two cases:

case (1) $x \geq 7$.  In that case
\begin{eqnarray*}
n+1 & = & 11\cdot x+13\cdot y + 1\\
& = & 11\cdot x+13\cdot y +  11 \cdot (-7)+13 \cdot 6\\
& = & 11\cdot (x-7) + 13\cdot (y+6).
\end{eqnarray*}
Since $x-7 \geq 0$ and $y+6 \geq 0$, we conclude that $P(n+1)$ holds.

case (2) $x < 7$.  In that case, since $142 \leq n=11\cdot x+13\cdot y$
and $11\cdot 6 + 13\cdot 4 < 142$, we must have $y \geq 5$.  So
\begin{eqnarray*}
n+1 & = & 11\cdot x+13\cdot y + 1\\
& = & 11\cdot x+13\cdot y + 11\cdot 6 + 13\cdot (-5)\\
& = & 11\cdot (x + 6) + 13\cdot (y-5).
\end{eqnarray*}
Since $x+6 \geq 0$ and $y-5 \geq 0$, we conclude that $P(n+1)$ holds.

Since one of these cases must hold, we conclude that $P(n+1)$ will
necessarily always hold.
\end{proof}

As a matter of fact, one can also make change of $\$141 = 10\cdot \$13 +
\$11$, but not \$140, as the reader may verify.}

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

\solution{Simple induction---on the number of moves (not the number of rings).

Let the induction hypothesis $P(k)$ be ``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 increase ordering.  Hence all
poles have rings in increasing order from the top after $k=1$ moves, that
is, $P(k+1)$ holds. \qed}

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

\solution{We choose an induction hypothesis which is slightly stronger
than the statement to be proved.  Namely, we allow there to be $n$
\emph{or more} $n$ rings initially stacked in increasing order on
\emph{any} given pole -- not necessarily the ``first'' pole.

To be precise, let the induction hypothesis, $P(n)$, be ``For any two
integers $i,j\in\set{1,2,3}$, suppose there are $n\ge 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 poles are larger than the top $n$
rings on pole $i$.  Then there is a way to move the top $n$ rings on pole
$i$ to pole $j$ in $2^n-1$ steps.''

Notice that it follows as a special case of $P(n)$, that there is a way to
move $n$ rings stacked in order on pole 1 onto pole 2 in $2^n-1$ steps, as
required.

Now we prove $P(n)$ by induction.

{\em Base case:} $P(1)$ is true because the single ring on pole $i$ can be
moved in $2^1-1 =1$ step onto pole $j$, because the ring on top of pole
$j$, if any, is larger than the ring on pole $i$.

{\em Inductive case:} Assume $P(n)$ holds for some integer $n \ge 1$.

We prove $P(n+1)$ as follows: assume that there are $n+1$ rings in
increasing order on top of pole $i$, and that the rings on top of the
other two poles are larger than the $n+1$ on top of pole $i$.  By
hypothesis, we can move the top $n$ rings from pole $i$ to the other pole
than $j$ in $2^n-1$ moves.  Now it is legal to move the top remaining ring
from pole $i$ to pole $j$.  Next it is possible, again by the induction
hypothesis, to move the top $n$ rings from the other pole to pole $j$ in
$2^n-1$ more steps.  The net result is that the $n+1$ rings on pole $i$
have beem moved to pole $j$ in $(2^n-1) + 1 + (2^n-1) = 2^{n+1}-1$ legal
moves, which proves $P(n+1)$.}

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

\solution{Similar to the previous part, noting that on a step when the
$n+1$st largest ring on pole $i$ is first moved to another pole, the first
$n$ must, by part~(a), appear in order on top of the
remaining pole, so by 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 stack $j$ for the last time.}

\eparts

\end{problems}

\end{document}

