\instatements{\newpage}

\begin{problem}
The Division Algorithm is an (oddly-named) theorem which says that if
you divide an integer $n$ by a positive integer $d$, then you get a
quotient and a small remainder.  Here is a formal statement:

\begin{theorem*}[Division Algorithm]
Let $n$ and $d$ be integers, with $d$ positive.  Then there exist
unique integers $q$ and $r$ such that $n = q d + r$ and $0 \leq r <
d$.
\end{theorem*}

Here is a ``proof'' that appears in a certain number theory textbook:

\begin{proof}
Let $S$ be the set of positive integers that are greater than $n / d$.
By the well-ordering property, $S$ contains a smallest element $t$;
thus, $t - 1 \leq n / d < t$.  Let $q = t - 1$; then $qd \leq b < (q +
1)d$.  If we set $r = b - qd$, then $n = qd + r$ and $0 \leq r < d$.
\end{proof}

\bparts

\ppart This proof contains two major errors.  Can you find at least
one?  (This is actually the first proof in the book!)  Discuss your
ideas with your recitation instructor.

\solution[\vspace{1.5in}]{
\begin{enumerate}

\item The theorem allows $n$ to be negative, but the proof does not
work in this case.  In particular, $n / d$ could be a big negative
number, and $t$ is positive by definition.  If so, there's no way that
the inequality $t - 1 \leq n / d < t$ holds.

\item The theorem asserts that $q$ and $r$ both \textit{exist} and are
\text{unique}.  The proof at least attempts to show that $q$ and $r$
exist, but doesn't address uniqueness.  This would require showing
that there is no different pair of numbers $q'$ and $r'$ such that $n
= q'd + r'$ and $0 \leq r' < d$.

\end{enumerate}
}

\ppart Let's prove the Division Algorithm correctly.  First, we must
show that a suitable divisor $d$ and quotient $r$ \textit{exist}.
Select $r$ using the the well-ordering principle.

\solution[\vspace{1.5in}]{
First, we show that the equation $n = qd + r$ holds for {\em some} $r
\geq 0$.  If $n$ is positive, then the equation holds when $q = 0$ and
$r = n$.  If $n$ is not positive, then the equation holds when $q = n$
and $r = n(1 - d) \geq 0$.  Thus, by the well-ordering principle,
there must exist a {\em smallest} $r \geq 0$ such that the equation
holds.  Furthermore, $r$ must be less than $d$; otherwise, $n = (q +
1) d + (r - d)$ would be another solution with a smaller nonnegative
remainder, contradicting the choice of $r$.
}

\ppart Now we must show that the quotient $q$ and remainder $r$ are
\textit{unique}.  Begin by assuming for the purpose of obtaining a
contradiction that they are not.  Then there exist distinct pairs
$q_1, r_1$ and $q_2, r_2$ such that:
%
\begin{align*}
n & = q_1 d + r_1 \hspace{0.75in} (\text{where $0 \leq r_1 < d$}) \\
n & = q_2 d + r_2 \hspace{0.75in} (\text{where $0 \leq r_2 < d$})
\end{align*}

\solution{
Subtracting the second equation from the first gives:
%
\[
0 = (q_1 - q_2) d + (r_1 - r2)
\]
%
Now the difference between the remainders $r_1$ and $r_2$ must be less
than $d$.  This implies that the absolute value of $(q_1 - q_2) d$
must also be less than $d$, which means that $q_1 - q_2 = 0$.  But
this means that $r_1 - r_2 = 0$ as well.  Therefore, the pairs $q_1,
r_1$ and $q_2, r_2$ are actually the same, which is a contradiction,
and so the quotient and remainder are unique.
}

\eparts

\end{problem}

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

Now one way to find an invariant is to compute a bunch of reachable
states and look for what they have in common.  For many problems like
this one, arranging the reachable states in a table can make a pattern
visually apparent.

{\footnotesize
\begin{tabular}{cc}
\text{\# green} &
\begin{tabular}{ccccccccccccccccc}
&\multicolumn{16}{c}{\text{\# red}} \\
 &0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15 \\
0& & &*&*& & & &*&*& & & &*&*& &  \\
1& & & &*&*& & & &*&*& & & &*&*&  \\
2&*& & & &*&*& & & &*&*& & & &*&* \\
3&*&*& & & &*&*& & & &*&*& & & &* \\
4& &*&*& & & &*&*& & & &*&*& & &  \\
5& & &*&*& & & &*&*& & & &*&*& &  \\
6& & & &*&*& & & &*&*& & & &*&*&  \\
7&*& & & &*&*& & & &*&*& & & &*&* \\
8&*&*& & & &*&*& & & &*&*& & & &* \\
9& &*&*& & & &*&*& & & &*&*& & &  \\
10& & &*&*& & & &*&*& & & &*&*& &  \\
11& & & &*&*& & & &*&*& & & &*&*&  \\
12&*& & & &*&*& & & &*&*& & & &*&*
\end{tabular}
\end{tabular}}