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

%\showsolutions
\hidesolutions

\newtheorem{false-theorem}[theorem]{False Theorem}

\begin{document}

\recitation{5}{February 16, 2005}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\insolutions{

\section{Well-ordering principle}

\textbox{
\centerline{
Every \emph{non-empty} set of \emph{natural} numbers 
has a \emph{minimum} element. 
}}

\noindent
Do you believe this statement? Seems obvious, right? Well, it is. But
don't fail to realize how tight it is. Crucially, it talks about a
\emph{non-empty} set ---otherwise, it would clearly be false. And it
also talks about \emph{natural} numbers ---otherwise, it might again
be false: think for example what would happen with the integers, or 
even the positive rational numbers.

This statement has a name, it is called \textbf{the well-ordering
principle}. And, as most things we give names to, it's important. Why? 
Because it is equivalent to induction. 
\begin{center}
\emph{Something can be proved by induction iff it can be proved
by the well-ordering principle.}
\end{center}
We could go on and give a general proof of this, but we
won't. Instead, we'll just convince ourselves of it by going through an
example. We'll reprove something that in the very first lecture (see
Lecture Notes ``Induction~I'') was proved by induction. Read the next page.

\noindent
For reference, here is the outline that a proof by the well-ordering
principle has. (Compare it with the corresponding outline of a proof
by strong induction.)

\textbox{
To prove that ``$P(n)$ is true for all $n\in\mathbb{N}$'' using the
well-ordering principle:  
\begin{itemize}
\item Use proof by contradiction.
\item Assume that $P(n)$ has \emph{counterexamples}. 
      I.e., that $P(n)$ is false on at least one $n$.
\item Define the set of counterexamples 
      $C=\{n\in\mathbb{N}\mid \neg P(n)\}$. 
\item Invoke the well-ordering principle to select the minimum
      element $c$ of $C$.
\item Since $c$ is \emph{the smallest counterexample} to $P(n)$,
      conclude that both $\neg P(c)$ and $P(0),P(1),\dots,P(c-1)$. Use
      these to arrive at a contradiction. Watch out: the list
      $0,1,\dots,c-1$ will contain no numbers at all if $c=0$.
\item Conclude that $P(n)$ must have no counterexamples. Namely, that
      $(\forall n) P(n)$.
\end{itemize}
}

\newpage

\begin{theorem*}
For all $n\in\mathbb{N}$:\quad
$
1 + 2 + 3 + \cdots + n = \tfrac{n(n+1)}{2}
$.
\end{theorem*}

\begin{proof}
By contradiction. Assume that the theorem is
\emph{false}. Then, some natural numbers serve as
\emph{counterexamples} to it. Let's collect them in a set: 
$$
C =     \bigl\{\: 
        n\in\mathbb{N} 
        \:\:\mid\:\:
        1 + 2 + 3 + \cdots + n \neq \tfrac{n(n+1)}{2}
        \:\bigr\}.
$$
By our assumption that the theorem admits counterexamples, $C$ is a
non-empty set of natural numbers. So, by the well-ordering principle,
$C$ has a minimum element, call it~$c$. That is, $c$ is the
\emph{smallest counterexample} to the theorem.  

\noindent
Since $c$ is a counterexample ($c\in C$), we know that 
$$
        1 + 2 + 3 + \cdots + c \neq \tfrac{c(c+1)}{2}.
$$
Since $c$ is the smallest counterexample ($c$ minimum of $C$), we
know the theorem holds for all natural numbers smaller than
$c$. (Otherwise, at least one of them would also be in $C$ and would
therefore prevent $c$ from being the minimum of $C$.) [$\ast$] In
particular, the theorem is true for $c-1$. That is, 
$$
        1 + 2 + 3 + \cdots + (c-1) = \tfrac{(c-1)c}{2}.
$$
But then, adding $c$ to both sides we get
$$
1 + 2 + 3 + \cdots + (c-1) + c 
        = \tfrac{(c-1)c}{2} + c \\\qquad
        = \tfrac{c^2 - c + 2c}{2} \\
        = \tfrac{c(c+1)}{2},
$$
which means the theorem does hold for $c$, after all! That is, $c$ is
not a counterexample. But this is a contradiction. And we are done.

\noindent
Well, almost. Our argument contains a bug. Everything we said
after~[$\ast$] bases on the fact that $c-1$ actually exists. That is,
that there is indeed some natural number smaller than $c$. How do we
know that? How do we know that $c$ is not~0? Fortunately, this can be
fixed. We know $c\neq 0$ because $c$ is a counterexample whereas $0$
is not, as $0=0(0+1)/2$.
\end{proof}

\newpage
}



\section{Problem: Well-ordering principle}

Here is the geometric sum formula, which you proved in a previous
recitation. 
$$
1 + r + r^2 + r^3 + \ldots + r^n = \frac{1 - r^{n+1}}{1 - r}
$$
Use the well-ordering principle to prove that, when $r \neq 1$, the
formula is true for all $n\in\mathbb{N}$.  
\emph{Prepare a complete, careful solution!}


\solution{
\begin{proof}
By contradiction.  Suppose the theorem is not true on all natural
numbers, but instead it admits some counterexamples. Let $C$ be the
set of these counterexamples:
$$
C =     \bigl\{ 
        n\in\mathbb{N}
        \;\mid\;
        1 + r + r^2 + \cdots + r^n \neq \tfrac{1 - r^{n+1}}{1 - r} 
        \bigr\}.
$$
By our assumption, $C$ is a non-empty set of natural numbers. So, the
well-ordering principle guarantees $C$ has a minimum element $c$. So,
$c$ is \emph{the smallest counterexample} to the theorem.


\noindent
Because $c$ is a counterexample, we know 
$$
        1 + r + r^2 + \cdots + r^c \neq \tfrac{1 - r^{c+1}}{1 - r}. 
$$
Because $1=(1-r^1)/(1-r)$, we know $0$ is not a counterexample, and
therefore $c>0$. 

\noindent
Because $c$ is the smallest counterexample, we know all numbers
smaller than $c$ satisfy the theorem ---and such numbers do exist, as
$c>0$. In particular, $c-1$ satisfies the theorem
$$
        1 + r + r^2 + \cdots + r^{c-1} = \tfrac{1 - r^c}{1 - r}. 
$$
But then, adding $r^c$ to both sides of the equation, we get
$$
1 + r + r^2 + \cdots + r^{c-1} +r^c 
        = \tfrac{1 - r^c}{1 - r} + r^c \qquad
        = \tfrac{1}{1-r}[1-r^c + r^c - r^{c+1}]
        = \tfrac{1-r^{c+1}}{1-r}
$$
which implies $c$ is not really a counterexample, a
contradiction. 

\noindent 
Therefore, there can't be any counterexamples to the theorem. The
theorem is true. 
\end{proof}
}

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

\newpage

\section{Problem: A robot}

A robot lives on a two dimensional grid and is free to walk
around. However each move it makes is always one step north or south 
\emph{and} one step east or west. Its purpose in life is to
reach point $(1,0)$. Unfortunately, the robot was born at point
$(0,0)$. Prove that it will never see how point $(1,0)$ looks like.

\noindent
\solution{
The approach that seems reasonable is to use induction on the number
$n$ of moves made by the robot. But we must be careful in selecting
the inductive hypothesis $P(n)$. If it simply corresponds to what we
want to prove ---that is, if it simply is ``after $n$ steps the robot
is not at point $(1,0)$''--- we are bound to encounter the same
problems as in class against the $9$-Number Puzzle. So, we must prove
something stronger.

\noindent
Trying out several paths that the robot might take, we soon see that
the robot can reach only points that lie on the line $x+y=0$ and
every other parallel of it. One way to describe this set of positions
is to say that \emph{a point $(x,y)$ belongs to it iff the sum $x+y$
is even}. We are now ready to prove the following theorem, which
is stronger than the one we were asked to prove.

\begin{theorem*}
The sum of the robot's coordinates is always even. 
\end{theorem*}


\begin{proof}
The proof is by (simple) induction on the number $n\in\mathbb N$ of
moves made by the robot. The inductive hypothesis $P(n)$ is this:
after $n$ moves, the sum of the robot's coordinates is even.

\noindent\textbf{Base case:} We show that $P(0)$ is true. Indeed,
after $0$ steps, the robot is still at its birthpoint $(0,0)$, and the
sum of its coordinates is $0+0=0$, as required.

\noindent\textbf{Inductive step:} We show that $P(n)$ implies
$P(n+1)$, for all $n\in\mathbb N$. So, fix any $n\in\mathbb N$ and
assume that $P(n)$ is true; that is, after its $n$th move, the robot
is at a position $(x,y)$ such that $x+y$ is even. 

\noindent
After the $n+1$st moves, the robot will have moved one step north or
south (which changes its x-coordinate by~1) \emph{and} one step east
or west (which also changes its y-coordinate by~1). So, if $(x',y')$
is the new point, we have 
$$
x' = x \pm 1 \qquad\text{and}\qquad y' = y \pm 1
$$
so that the new sum of coordinates is
$$
x'+y' = (x\pm 1) + (y\pm 1) = (x+y) + [(\pm 1) + (\pm 1)] = (x+y) + d
$$
where $d\in\{-2,0,+2\}$. In all cases, $x'+y'$ is a sum of two
even numbers. So, $P(n+1)$ holds.

\noindent
Therefore, by induction, $P(n)$ is true for all $n\in\mathbb N$. The theorem
holds. 
\end{proof}

\noindent
Now, to prove that the robot never reaches point $(1,0)$, we just need
to observe that the sum $1+0 = 1$ is not even.
}


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

\newpage



\section{Square Infection}

The following problem is fairly tough until you hear a certain
one-word clue.  Then the solution is easy!  Suppose that we have an $n
\times n$ grid, where certain squares are \textit{infected}.  Here is
an example where $n = 6$ and infected squares are marked $\times$.
$$
\begin{array}{|c|c|c|c|c|c|}
\hline
\times& & & &\times& \\ \hline
 &\times& & & & \\ \hline
& &\times&\times& & \\ \hline
& & & & & \\ \hline
& &\times& & & \\ \hline
& & &\times& &\times \\ \hline
\end{array}
$$

\noindent Now the infection begins to spread in discrete
time steps.  Two squares are considered \textit{adjacent} if they
share an edge; thus, each square is adjacent to 2, 3 or 4 others.  A
square is infected in the next time step if either
\begin{itemize}
\item the square was previously infected, or
\item the square is adjacent to \textit{at least two} already-infected squares.
\end{itemize}
In the example, the infection spreads as shown below.
$$
\begin{array}{|c|c|c|c|c|c|}
\hline
\times& & & &\times& \\ \hline
 &\times& & & & \\ \hline
& &\times&\times& & \\ \hline
& & & & & \\ \hline
& &\times& & & \\ \hline
& & &\times& &\times \\ \hline
\end{array}
\;\;\;\;\Rightarrow\;\;\;\;
\begin{array}{|c|c|c|c|c|c|}
\hline
\times&\times& & &\times& \\ \hline
\times&\times&\times& & & \\ \hline
&\times&\times&\times& & \\ \hline
& &\times& & & \\ \hline
& &\times&\times& & \\ \hline
& &\times&\times&\times&\times \\ \hline
\end{array}
\;\;\;\;\Rightarrow\;\;\;\;
\begin{array}{|c|c|c|c|c|c|}
\hline
\times&\times&\times& &\times& \\ \hline
\times&\times&\times&\times& & \\ \hline
\times&\times&\times&\times& & \\ \hline
&\times&\times&\times& & \\ \hline
& &\times&\times&\times& \\ \hline
& &\times&\times&\times&\times \\ \hline
\end{array}
$$
Over the next few time-steps, the entire grid becomes infected.

\begin{theorem*}
An $n \times n$ grid can become completely infected 
only if at least $n$ squares are initially infected.
\end{theorem*}

\noindent
Prove this theorem using induction and some additional reasoning.  If
you are stuck, ask your recitation instructor for the one-word clue!

\noindent
\solution{
Define the \term{perimeter} of an infected region to be the number of
edges with infection on exactly one side.  Let $I$ denote the
perimeter of the initially-infected region.

\begin{proof}
We use induction on the number of time steps $k$ to prove that the
perimeter of the infected region never increases.  The inductive
hypothesis $P(k)$ is this: after $k$ time steps, the perimeter of the
infected region is at most $I$.

\noindent \textit{Base case:} $P(0)$ is true by definition; the
perimeter of the infected region is at most $I$ after 0 time steps,
because $I$ is defined to be the perimeter of the initially-infected
region.

\noindent \textit{Inductive step:} We now show that $P(k)$ implies
$P(k+1)$ for all $k \geq 0$.  So, fix any $k\geq 0$ and assume that
$P(k)$ is true; that is, after $k$ steps, the perimeter of the
infected region is at most $I$.  

\noindent
After step $k + 1$ the primeter can only change because some squares
are newly infected.  By the rules above, each newly-infected square is 
adjacent to at least two previously-infected squares.  Thus, for each
newly-infected square, at least two edges are removed from the
perimenter of the infected region, and at most two edges are added to
the perimeter. Therefore, the perimeter of the infected region can not
increase and is at most $I$ after $k + 1$ steps as well.  Hence,
$P(k+1)$ is true.  

\noindent
By induction, we conclude that $P(k)$ is true for all $nk \geq 0$.
\end{proof}

\noindent
Now, if an $n \times n$ grid is completely infected, then the
perimeter of the infected region is $4n$.  Thus, the whole grid can
become infected only if the perimeter is initially at least $4n$.
Since each square has perimeter 4, at least $n$ squares must be
infected initially.}


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

\end{document}

