\documentclass[12pt]{article}
\usepackage{light}

%\hidesolutions
\showsolutions

\begin{document}

\recitation{3}{September 17, 2004}

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

\insolutions{
\section{Well-Ordering}

Here is a statement that appears, at first glance, to be as useless as
it is obvious.

\textbox{\textbf{Well-Ordering Principle. }  Every nonempty subset of
the natural numbers has a smallest element.}

\noindent The first glance is deceiving!  As for obvious, note that
the well-ordering principle would be false if the natural numbers were
replaced by, say, the real numbers, the integers, or even the
nonnegative rational numbers.  So the well-ordering principle is
capturing something special about the natural numbers.

As for useless, everything provable with ordinary or strong induction
can equally well be proved with the well-ordering principle!  Thus,
well-ordering is as powerful as the most important proof technique
used in computer science.  Let's do an example to demonstrate its
utility.

\begin{theorem}
There is no solution over the positive integers to the equation:
%
\[
4a^3 + 2b^3 = c^3
\]
\end{theorem}

\begin{proof}
We use contradiction and the well-ordering principle.  Let $S$ be the
set of all positive integers $a$ such that there exist positive
integers $b$ and $c$ that satisfy the equation.

Assume for the purpose of obtaining a contradiction that $S$ is
nonempty.  Then $S$ contains a smallest element $a_0$ by the
well-ordering principle.  By the definition of $S$, there exist
corresponding positive integers $b_0$ and $c_0$ such that:
%
\[
4a_0^3 + 2b_0^3 = c_0^3
\]
%
The left side of this equation is even, so $c_0^3$ is even, so $c_0$
is even.  Thus, there exists an integer $c_1$ such that $c_0 = 2 c_1$.
Substituting into the preceding equation and then dividing both sides
by 2 gives:
%
\[
2 a_0^3 + b_0^3 = 4 c_1^3
\]
%
Now $b_0^3$ must be even, so $b_0$ is even.  Thus, there exists an
integer $b_1$ such that $b_0 = 2 b_1$.  Substituting into the
preceding equation and dividing both sides by 2 again gives:
%
\[
a_0^3 + 4 b_1^3 = 2 c_1^3
\]
%
From this equation, we know that $a_0^3$ is even, so $a_0$ is even.
Thus, there exists an integer $a_1$ such that $a_0 = 2 a_1$.
Substituting into the previous equation one last time and dividing by
2 one last time gives:
%
\[
4 a_1^3 + 2 b_1^3 = c_1^3
\]

Evidently, $a = a_1$, $b = b_1$, and $c = c_1$ is another solution to
the original equation, and so $a_1$ is an element of $S$.  But this is
a contradiction, because $a_1 < a_0$ and $a_0$ was defined to be the
smallest element of $S$.  Therefore, our assumption was wrong, and the
original equation has no solutions over the positive integers.
\end{proof}

This argument is quite similar to the proof that $\sqrt{2}$ is
irrational.  In fact, looking back, we implicitly relied on the
well-ordering principle in that proof when we claimed that a rational
number could be written as a fraction in \textit{lowest terms}.  We've
been using the well-ordering principle on the sly since Day 1!

Induction, strong induction, and well-ordering are logically
equivalent, so the best choice for a particular application is the one
that you think gives the clearest proof.  In practice, induction and
strong induction are more commonly used than well-ordering.  But for
the occasional problem, like proving that $\sqrt{2}$ is irrational, an
argument based on well-ordering may be much nicer.}

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

\section{Problem: The Pirate Raid}

Three pirates are considering an attack on the {\em Pi\~{n}ata}, a
Spanish galleon laden with $n \geq 20$ pieces of gold.  Redbeard
insists that his share of the treasure be a multiple of 5 gold pieces,
Bluebeard insists that his share be a multiple of 7 gold pieces, and
Blackbeard demands a multiple of 9 gold pieces.  Furthermore, no
pirate can tolerate treasure going to waste; if that is unavoidable,
the pirates will surely have a fatal quarrel.

For example, if there were 12 gold pieces aboard, then Redbeard could
take 5, Bluebeard 7, and Blackbeard 0.  However, if there were 13 gold
pieces aboard, then the pirates would kill each other.

Can the pirates safely attack the {\em Pi\~{n}ata}?  Use strong
induction to prove that your answer is correct.

\solution{The pirates can safely attack the Pi\~{n}ata.  The
proof is by strong induction on $n$, the number of gold pieces aboard.

Let $P(n)$ be the proposition that $n$ is of the form $5x + 7y + 9z$,
where $x$, $y$, and $z$ are nonnegative integers.  First, we show that
$P(n)$ holds for all $n$ between 20 and 24.

\begin{eqnarray*}
20 & = & 5 \cdot 4 + 7 \cdot 0 + 9 \cdot 0 \\
21 & = & 5 \cdot 1 + 7 \cdot 1 + 9 \cdot 1 \\
22 & = & 5 \cdot 3 + 7 \cdot 1 + 9 \cdot 0 \\
23 & = & 5 \cdot 0 + 7 \cdot 2 + 9 \cdot 1 \\
24 & = & 5 \cdot 2 + 7 \cdot 2 + 9 \cdot 0
\end{eqnarray*}

Now we must show that $P(n)$ is true assuming that $P(20), \ldots, P(n
- 1)$ are all true, where $n \geq 25$.  Then, in particular, we know
that $P(n - 5)$ is true; that is, there is a way of dividing up $n -
5$ gold pieces among the three pirates with none going to waste.  We
can divide $n$ gold pieces in the same way, giving the 5 extras to
Redbeard.  This shows that $P(n)$ is true as well.  Therefore, $P(n)$
is true for all $n \geq 20$ by strong induction.
}

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

\instatements{\newpage}

\section{Problem: The Temple of Forever}

Each monk entering the Temple of Forever is given a bowl with 15 red
beads and 12 green beads.  Each time the Gong of Time rings, a monk
must do one of two things:

\begin{enumerate}

\item If he has at least 3 red beads in his bowl, then he may remove 3
red beads and add 2 green beads.

\item He may replace each green bead in his bowl with a red bead and
replace each red bead in his bowl with a green bead.

\end{enumerate}

\noindent A monk may leave the Temple of Forever only when he has
exactly 5 red beads and 5 green beads in his bowl.

\begin{theorem*}
No one ever leaves the Temple of Forever.
\end{theorem*}

Prove this theorem by induction.  Begin by searching for an invariant
that holds initially and is maintained by each operation, but would be
violated by the condition required for departure.

\solution{
\begin{proof}
We use induction on the number of gong rings.  Let $P(n)$ be the
proposition that after $n$ rings, the number of red beads in the
monk's bowl minus the number of green beads is equal to $5k+2$ or
$5k+3$ for some integer $k$.

\noindent \textit{Base case:} $P(0)$ is true because initially (after
zero rings) the number of red beads minus the number of green beads is
$15 - 12 = 5 \cdot 0 + 3$.

\noindent \textit{Inductive step:} Now assume that $P(n)$ holds after
$n$ gong rings, where $n \geq 0$.  Let $r$ denote the number of red
beads in the monk's bowl, and let $g$ denote the number of green
beads.  In these terms, we are assuming that $r - g$ is equal to $5k +
2$ or $5k + 3$ for some integer $k$.  After $n + 1$ gong rings, there
are two cases to consider, depending on the monk's action:

\begin{enumerate}

\item If $r \geq 3$, then the monk may have replaced 3 red beads with
2 green beads.  Thus, the number of red beads minus the number of
green becomes:
%
\[
(r - 3) - (g + 2) = (r - g) - 5
\]
%
This is equal to either $5 (k - 1) + 2$ or $5 (k - 1) + 3$, so
$P(n+1)$ is true.

\item Alternatively, the monk may have exchanged every red bead for a
green bead and vice versa.  In this case, the number of reds minus the
number of greens becomes $g - r$.  If $r - g = 5k + 3$, then $g - r =
5 (-k) - 3 = 5 (-k-1) + 2$.  If $r - g = 5k + 2$, then $g - r = 5 (-k)
- 2 = 5 (-k-1) + 3$.  Thus, $P(n+1)$ is again true.

\end{enumerate}

Therefore, $P(n)$ implies $P(n+1)$ for all $n \geq 0$.

By the induction principle, $P(n)$ is true for all $n \geq 0$.  Since
the number of red beads minus the number of greens is always of the
form $5k+2$ or $5k+3$ and the difference required to leave the temple
does not match either form, no monk can ever leave the Temple of
Forever.
\end{proof}
}

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

\end{document}
