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

%\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{2, Fri}            % !! start the paper


%STRONG INDUCTION, new

\begin{problem}
What amounts of postage can be made from 6\textcent\ stamps and 10\textcent\
stamps?  Prove it.

\solution{6\textcent, 10\textcent, 12\textcent, and every even number of
cents $\geq 16$\textcent.

We define our induction hypothesis $P(n)$ to be the following: an even
amount $n$ of postage can be assembled from 6\textcent\ stamps and
10\textcent\ stamps, for $n\geq 16$.

Cases $n= 16, 18, 20$\textcent\ can be gotten explicitly.  Then for
even $n \geq 22$ we do the following: Assuming our hypothesis holds
for $k\leq n$ we assemble $n-4$\textcent\ and add a 6\textcent\ stamp
to get $n+2$ which is the next even number after $n$.  We can't get an
odd value of postage because 6 and 10 are both even.}
\end{problem}

%STRONG INDUCTION, F01 ps2

\begin{problem}
Pinpoint, and illustrate with a counterexample, \emph{exactly}
where the following proof goes awry.

An integer, $m$, \emph{divides} an integer, $n$, in symbols, $m
\divides n$, iff there is an integer $k$ such that $km=n$.

\begin{falseclm*}
For any positive integers $p, x_1, x_2,\ldots, x_n$, if $p \divides
x_1x_2\cdots x_n$, then $p \divides x_i$ for some $i$ between 1 and $n$.
\end{falseclm*}

\begin{falseproof}
(by strong induction on $n$.)

The induction hypothesis is the False Claim itself.

\textbf{Base case} ($n = 1$): When $n=1$, we have $p\divides x_1$,
therefore we can let $i=1$ and conclude $p\divides x_i$.

\textbf{Induction step}: Now assuming the claim holds for all $k\leq n$,
we must prove it for $n+1$.

So suppose $p\divides x_1x_2\cdots x_{n+1}$.  Let $y_n = x_n x_{n+1}$, so
$x_1x_2\cdots x_{n+1} = x_1x_2\cdots x_{n-1}y_n$.  Since the righthand
side of this equality is a product of $n$ terms, we have by induction that
$p$ divides one of them.  If $p\divides x_i$ for some $i < n$, then we
have the desired $i$.  Otherwise $p\divides y_n$.  But since $y_n$ is a
product of the two terms $x_n, x_{n+1}$, we have by strong induction that
$p$ divides one of them.  So in this case $p \divides x_i$ for $i = n$ or
$i = n+1$.
\end{falseproof}

\solution{The statement ``we have by strong induction that $p$ divides
one of them'' is the place where the proof breaks down: it appeals to
strong induction to justify applying the induction hypothesis for $2=k\leq
n$.  But the base case was $n=1$, so we can't assume $2 \leq n$.  Note
that the reasoning above is fine for every $n\geq 2$, so the whole proof
would be fine if we had an argument to prove the claim for $n+1=2$.  But
of course we can't prove it for $n+1=2$ because it isn't true: let $p=6,
x_1 =2, x_2 =3$.  Even though the reasoning is fine for every $n\geq 2$,
the fact that it failed for $n=1$ let us deduce a completely false
result.}

\end{problem}

%%Example from Spring99, tutorial 2, Least Number Principle

\begin{problem}

Here's a different proof that the square root of 2 is irrational, this one
based on the Least Number Principle.

\begin{proof}
The proof is by contradiction.

Assume that the square root of 2 is rational.  Then $\sqrt{2}$ is equal to
$m / n$ for some positive integers $m$ and $n$.  So $n$ has the property
that
\begin{equation}\label{ns2}
n \text{ and } n\sqrt{2} \text{ are positive integers}.
\end{equation}
Now by the Least Number Principle, there must be a \emph{smallest}
positive integer, $n$, satisfying~(\ref{ns2}).  For this $n$, let $n_0
\eqdef n (\sqrt{2} - 1)$.  But then $n_0$ is smaller than $n$, and $n_0$
and $n_0\sqrt{2}$ are positive integers, a contradiction.
\end{proof}

\begin{problemparts}

\problempart Are you convinced by this proof?  Briefly explain.

In particular, why is $n_0$ an integer?

\solution{Because it equals $n\sqrt{2} - n$
and $n$ and  $n\sqrt{2}$ are integers by hypothesis.}

Why is $n_0$ positive?

\solution{Because $(\sqrt{2} -1) \approx 0.414\dots$ is positive.}

Why is $n_0$ smaller than $n$?

\solution{Because $(\sqrt{2}-1) < 0.415 < 1$.}

Why is $n_0\sqrt{2}$ a positive integer?

\solution{It's an integer because $n_0\sqrt{2} = (n\sqrt{2} - n)\sqrt{2}
= 2n - n\sqrt{2}$, which is again an integer because both terms are
integers.  It's positive because $2n - n\sqrt{2} = (2 - \sqrt{2})n > 0.58
n > 0$.}

\end{problemparts}

We can generalize this proof to prove that $\sqrt{k}$ is irrational for
integers $k$ other than 2.  Simply revise the next to last sentence to
read, ``\dots and let $n_0 \eqdef n (\sqrt{k} - \floor{\sqrt{k}})$''.  (For
any real number, $r$, the expression $\floor{r}$ denotes $r$ rounded
\emph{down} to the nearest integer.)

\begin{problemparts}
\problempart Are you convinced by this argument?  Explain.

\solution{You shouldn't be convinced because the conclusion is wrong,
For example, $\sqrt{k}$ is certainly rational if $k=4$.

The proof works for $\sqrt{k}$ as long as $k$ is not a perfect square.
But if $k$ is a perfect square, then the proof breaks down in the next to
last sentence: the number $n_0 (\sqrt{k} - \lfloor \sqrt{k} \rfloor)$ is
not positive in this case, but zero.}
\end{problemparts}

\end{problem}


\begin{problem}  %f01-ps2-6

We are given a chocolate bar with $m \times n$ squares of
chocolate, and our task is to divide it into $mn$ individual squares.  We
are only allowed to split one piece of chocolate at a time using a
vertical or a horizontal break.

For example, suppose that the chocolate bar is $2 \times 2$.  The
first split makes two pieces, both $2 \times 1$.  Each of these pieces
requires one more split to form single squares.  This gives a total of
three splits.

\begin{problemparts} \problempart Use strong induction to conclude the following:
\begin{theorem*}
To divide up a chocolate bar with $m \times n$ squares, we need at
most $m n - 1$ splits.
\end{theorem*}

\solution{This theorem does not immediately lend itself to an induction
proof, since there are two variables.  In general, propositions involving
several natural-valued variables can often be proved by using a sort of
nested induction.  However, in this case, we can get by with a
single-variable induction and a trick.

Intuitively, to break up a big chocolate bar, we need one split to
make two pieces, and then we can break up the two pieces recursively.
This suggests a proof using strong induction on the {\em size} of the
chocolate bar, where size is measured in chocolate squares.  Now
instead of a problem involving two variables (the two dimensions), we
have a problem in one variable (the size).  With this simplification,
we can prove the theorem using strong induction.

\begin{proof}
The proof is by strong induction on the size of the chocolate bar.  Let
$P(k)$ be the proposition that a chocolate bar of size $k$ requires at
most $k - 1$ splits.  

\emph{Base case, $k=1$}: $P(1)$ is true because there is only a single
square of chocolate, and $1 - 1 = 0$ splits are required.

\emph{Induction step}: We suppose $k \geq 1$ and any chocolate bar of size
$s$, where $1 \leq s \leq k$, requires at most $s-1$ splits.  We must now
show there is a way to split a chocolate bar of size $k+1$ with at most
$k$ splits.

To do this, first break the chocolate bar of size $k+1$ into two smaller
pieces of size $p$ and $q$ where $p + q = k + 1$.  This is certainly
possible because the size of the bar is at least two.  Now the pieces of
sizes $p$ and $q$ are between one and $k$, so by strong induction,
breaking these two pieces into single squares requires only $p - 1$ and $q
- 1$ splits, respectively.  The total number of splits required to break
the bar of size $k+1$ into single squares is therefore at most $1 + (p -
1) + (q - 1) = p + q - 1 = (k + 1) - 1 = k$.

This shows that $P(k)$ implies $P(k+1)$, and the claim is proved by
strong induction.
\end{proof}
}

\problempart The theorem proves that \emph{at most} $mn - 1$
splits are needed to divide up an $m$ by $n$ chocolate bar.  Could you do
better?

\solution{The proof really shows that exactly $s - 1$ splits are
needed.  Observe that in the induction step, no matter how we split the
bar into smaller bars of size $p$ and $q$, exactly $(p - 1) + (q - 1) = s
- 1$ splits are required.}
\end{problemparts}

\end{problem}


\iffalse
%% Original problem, recursively defined set (of arithmetic expressions);
%% modular arithmetic.

\begin{problem}
Define the set of \emph{Arithmetic Expressions} (AExp's) recursively as follows:
\begin{enumerate}

\item base cases:
\begin{enumerate}

\item a \emph{variable} is an AExp.

\item an \emph{integer} is an AExp.

\end{enumerate}
\item if $F,G$ are AExp's, the ($F$ + $G$) is an AExp called a \emph{sum}.

\item if $F,G$ are AExp's, then ($F \cdot G$) is an AExp called a \emph{product}.

\end{enumerate}
For example,
\[
(((3 \cdot x) + y) \cdot ((y\cdot (-5)) + 92)).
\]
Omitting unnecessary parentheses and the multiplication sign ($\cdot$), we
could write this in the easier to read form
\begin{equation}\label{ae1}
(3 x + y)(y(-5) + 92).
\end{equation}

The value of expression~\ref{ae1} depends on the values of $x$ and $y$ in
the obvious way.  For example, if $x=2$ and $y=1$, its value is $7\cdot87
=609$.
\begin{problemparts}

\problempart Prove that for any AExp, $E$, with variables $x_1, x_2,\dots$
and any $n>1$, if $k_1 \equiv l_1 \mod n$, $k_2 \equiv l_2 \mod n$, \dots,
the value of $E$ when the variables equal $k_1,k_2,\dots$ is $\equiv \mod
n$ to the value of $E$ when the variables equal $l_1,l_2,\dots$.

\problempart If an AExp is not constant, then the value of the expression
at some natural number assignment to its variables is not a prime.

\end{problemparts}
\end{problem}
\fi

\end{document}
