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

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

\begin{problem}

Given an unlimited supply of 5 cent and 7 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 5 cent
and 7 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 5 and 7 cent stamps.  The column
heading is the number of 5 cent stamps and the row heading is the number
of 7 cent stamps.

\[\begin{array}{c|ccccccc}
    & 0 & 1 & 2 & 3 & 4 & 5 &     \dots\\ \hline
  0 & 0 & 5 &10 &15 &20 &25 &     \dots\\
  1 & 7 &12 &17 &22 &27 & \dots & \\
  2 &14 &19 &24 &29 & \dots &   & \\
  3 &21 &26 &31 &36 & \dots &   & \\
  4 &28 &33 &38 & \dots &   &   & \\
  5 &35 &40 &\dots& &   &   & \\
  \vdots & \vdots & \vdots
  \end{array}\]

Looking at the table, a guess is that the possible postages are those
shown and every value of 24 or more cents.  Let's try to prove this last
part using strong induction.

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

Now let's preview the proof.  The induction hypothesis will be
\begin{eqnarray}\label{P}
P(n) & \eqdef & \text{$n+24$\textcent\ postage can be
produced using 5\textcent\ and 7\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)$, is that 24\textcent\
postage can be made, and from the table, it can, using two 5\textcent\ and
two 7\textcent\ stamps.

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

But we have to be careful.  If $n<4$, this method may not work, because we
would have to produce postage of less than 24\textcent, which may not be
possible.  So in this case we cannot use the trick of creating $(n+1)+24$
cents of postage from $n-4+24$ cents and a 5 cent stamp.  Fortunately,
making $(n+1)+24$ cents of postage for $n<4$ can easily be done
directly.

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

\textbf{Base case:} $n=0$: $P(0)$ holds because we can make 24\textcent\
postage using two 5\textcent\ and two 7\textcent\ stamps.

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

There are five cases:

\begin{enumerate}
\item $n+1=1$: To make $(n+1)+24 = 25$\textcent\ postage, use five
5\textcent\ stamps

\item $n+1 = 2$: To make 26\textcent\ postage, use one 5\textcent\ stamp
  and three 7\textcent\ stamps.

\item $n+1 = 3$:  To make 27\textcent\ postage, use four 5\textcent\ stamps
  and one 7\textcent\ stamp.

\item $n+1 = 4$:  To make 28\textcent\ postage, use four 7\textcent\ stamps.

\item $n+1 > 4$: We have $n \geq 4$, so $n-4 \geq 0$ and by strong
induction we may assume we can produce exactly $(n-4)+24$ cents of
postage.  With an additional 5\textcent\ stamp we can therefore produce
$(n+1)+24$ 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}


\begin{problem}
We consider integer solutions to the equation
\begin{equation}\label{eq}
4a^3 + 2b^3 = c^3
\end{equation}

\bparts

\ppart Use the Well-ordering Principle to prove that
there is no integer solution to equation~\eqref{eq} with $a>0$.

\solution{The proof is by contradiction.

Let $S$ be the set of all positive integers, $a$, such that there exist
integers, $b$, and, $c$, that satisfy equation~\eqref{eq}.

Assume for the purpose of obtaining a contradiction that $S$ is nonempty.
Then $S$ contains a smallest element, $a_0>0$, by the Well-ordering
Principle.  By the definition of $S$, there exist corresponding 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$.  Now substituting $2c_1$ for $c_0$ in this equation and
then dividing both sides by 2 gives:
\begin{equation}\label{2a0}
2 a_0^3 + b_0^3 = 4 c_1^3,
\end{equation}
so
\[ 
b_0^3 = 2(2 c_1^3 -a_0^3).
\]
This impies that $b_0^3$ is even, so $b_0$ is even.  Thus, there exists an
integer, $b_1$, such that $b_0 = 2 b_1$.  Substituting $2b_1$ for $b_0$
in~\eqref{2a0} and dividing both sides by 2 gives:
\begin{equation}\label{a03} 
a_0^3 + 4 b_1^3 = 2 c_1^3 
\end{equation} 
From~\eqref{a03}, we conclude 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$, where $a_1
>0$ since $a_0 >0$.  Substituting $2a_1$ for $a_0$ in~\eqref{a03} and
dividing by 2 one final time gives:
\[ 
4 a_1^3 + 2 b_1^3 = c_1^3 
\] 
So evidently, $a = a_1$, $b = b_1$, and $c = c_1$ is another solution to
the original equation~\eqref{eq}, 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 integer solutions with $a>0$.}

\ppart Show that the only integer solution to equation~\eqref{eq} is
$a=b=c=0$.

\solution{There are two cases left to consider: when $a<0$ or when $a=0$.

So let $S'$ be the set of all integers, $n>0$, such that there is an
integer solution to equation~\eqref{eq} with $a=-n$.  The previous
argument now goes through with $S'$ in place of $S$, proving that $S'$ is
empty.  So there is no solution with to equation~\eqref{eq} with $a<0$.

Finally, with $a=0$, to solve~\eqref{eq}, we need integers $b,c$ such that
\begin{equation}\label{2b}
2b^3=c^3.
\end{equation}
Now if $b=0$ in~\eqref{2b}, then obviously $c=0$, giving us the all-zero
solution.  On the other hand, if $b\neq 0$ in~\eqref{2b}, then $c/b$ would
be a rational cube root of 2, and we know there is none.  So the only
possibility is the all-zero solution.}

\eparts

\end{problem}

\end{document}
