\documentclass[11pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query
%\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

\begin{document} 
\inclassproblems{3, Fri.}                    % !! start the paper


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

\begin{problem}

Given an unlimited supply of 3 cent and 5 cent stamps, what postages are
possible?  Prove it using Strong Induction.  \hint Try some examples!
Which postage values between 1 and 25 cents can you construct from 3 cent
and 5 cent stamps?


\solution{Let's use our examples to first try to guess the answer and
then try to prove it.  Let's begin filling in a table that shows the
values of all possible combinations of 3 and 5 cent stamps.  The column
heading is the number of 5 cent stamps and the row heading is the number
of 3 cent stamps.

\[
\begin{array}{c|ccccccc}
  & 0 & 1 & 2 & 3 & 4 & 5 & \dots\\ \hline
  0 & 0 & 5 &10 &15 &20 &25 & \dots\\
  1 & 3 & 8 &13 &18 &23 & \dots  & \\
  2 & 6 &11 &16 &21 & \dots  &   & \\
  3 & 9 &14 &19 &24 & \dots  &   & \\
  4 &12 &17 &22 & \dots  &   &   & \\
  5 &15 &20 & \dots  &   &   &   & \\
  \dots & \dots & \dots
  \end{array}
  \]

  Looking at the table, a reasonable guess is that the possible postages are
  0, 3, 5, and 6 cents and every value of 8 or more cents.  Let's try to
  prove this last part using strong induction.

  \begin{claim}\label{3-5}
  For all $n \geq 8$, it is possible to produce $n$ cents of postage from
  3\textcent\ and 5\textcent\ stamps.
  \end{claim}

  Now let's preview the proof.  The induction hypothesis will be
  \begin{eqnarray}\label{P}
  P(n) & \eqdef & \text{if } n \geq 8, \text{ then $n$\textcent\ postage can be
  produced using 3\textcent\ and 5\textcent\ stamps}
  \end{eqnarray}

A proof by strong induction will have the same five-part structure as an
ordinary induction proof.  The base case, $P(0)$, won't be interesting
because $P(n)$ is \emph{vacuously} true for all $n <8$.

In the inductive step we have to show how to produce $n+1$ cents of
postage, assuming the strong induction hypothesis that we know how to
produce $k$\textcent\ of postage for all values of $k$ between 8 and $n$.
A simple way to do this is to let $k= n-2$ and produce $k$\textcent\ of
postage; then add a 3\textcent\ stamp to get $n+1$ cents.

But we have to be careful; there is a pitfall in this method.  If $n+1$ is
8, 9 or 10, then we can not use the trick of creating $n+1$ cents of
postage from $n-2$ cents and a 3 cent stamp.  In these cases, $n-2$ is
less than 8.  None of the strong induction assumptions help us make less
than 8\textcent\ postage.  Fortunately, making $n+1$ cents of postage in
these three cases can be easily done directly.

\begin{proof}
The proof is by strong induction.  The induction hypothesis, $P(n)$, is
given by~(\ref{P}).

\textbf{Base case:} $n=0$: $P(0)$ is true vacuously.

\textbf{Inductive step:} In the inductive step, we assume that it is possible 
to produce postage worth $8, 9, \dots, n$ cents in order to prove that it is 
possible to produce postage worth $n+1$ cents.

There are four cases:

\begin{enumerate}
\item $n+1 < 8$:  So $P(n+1)$ holds vacuously.

\item $n+1 = 8$: $P(n+1)$ holds because we produce $8$\textcent\ postage
using one 3\textcent\ and one 5\textcent\ stamp.

\item $n+1 = 9$: $P(n+1)$ holds by using three 3\textcent\ stamps.

\item $n+1 = 10$: $P(n+1)$ holds by using two 5\textcent\ stamps.

\item $n+1 > 10$: We have $n \geq 10$, so $n-2 \geq 8$ and by strong
induction we may assume we can produce exactly $n-2$ cents of postage.
With an additional 3\textcent\ stamp we can therefore produce $n+1$ cents
of postage.
\end{enumerate}
So in every case, $P(0) \wedge P(1) \wedge \dots P(n) \implies P(n+1)$.
By strong induction, we have concluded that $P(n)$ is true for all $n \in
\naturals$.
\end{proof}

}

\end{problem}

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

%\instatements{
%\newpage
%\vspace{1in}
%\centerline{\resizebox{7in}{!}{\includegraphics{grid.eps}}} }

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

\instatements{\newpage}

\begin{problem}

Use the Well-ordering Principle to prove that there is no solution over
the positive integers to the equation:
\[
4a^3 + 2b^3 = c^3.
\]

\solution{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, and therefore
$c_0$ is also 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 also 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.  

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 from early on!}

\end{problem}

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

%\instatements{
%\newpage
%\centerline{\resizebox{7in}{!}{\includegraphics{grid.eps}}}
%}

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

\end{document}
