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

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

\begin{document}

\lecture{Induction, II.}{September 16, 2004}

\section{Good Proofs and Bad Proofs}

In a purely technical sense, a mathematical proof is verification of a
proposition by a chain of logical deductions from a base set of
axioms.  But the \textit{purpose} of a proof is to provide readers
with compelling evidence for the truth of an assertion.  To serve this
purpose effectively, more is required of a proof than just logical
correctness: a good proof must also be clear.  These goals are
complimentary; a well-written proof is more likely to be a correct
proof, since mistakes are harder to hide.  Here are some tips on
writing good proofs:

\begin{description}

\item[State your game plan.]  A good proof begins by explaining the
general line of reasoning, e.g. ``We use induction'' or ``We argue by
contradiction''.  This creates a rough mental picture into which the
reader can fit the subsequent details.

\item[Keep a linear flow.] We sometimes see proofs that are like
mathematical mosaics, with juicy tidbits of reasoning sprinkled
judiciously across the page.  This is not good.  The steps of your
argument should follow one another in a clear, sequential order.

\item[Explain your reasoning.]  Many students initially write proofs
the way they compute integrals.  The result is a long sequence of
expressions without explantion.  This is bad.  A good proof usually
looks like an essay with some equations thrown in.  Use complete
sentences.

\item[Avoid excessive symbolism.]  Your reader is probably good at
understanding words, but much less skilled at reading arcane
mathematical symbols.  So use words where you reasonably can.

\item[Simplify.]  Long, complicated proofs take the reader more time
and effort to understand and can more easily conceal errors.  So a
proof with fewer logical steps is a better proof.

\item[Introduce notation thoughtfully.]  Sometimes an argument can be
greatly simplified by introducing a variable, devising a special
notation, or defining a new term.  But do this sparingly, since you're
requiring the reader to remember all this new stuff.  And remember to
actually \textit{define} the meanings of new variables, terms, or
notations; don't just start using them.

\item[Structure long proofs.]  Long program are usually broken into a
heirarchy of smaller procedures.  Long proofs are much the same.
Facts needed in your proof that are easily stated, but not readily
proved are best pulled out and proved in a preliminary lemmas.  Also,
if you are repeating essentially the same argument over and over, try
to capture that argument in a general lemma and then repeatedly cite
that instead.

\item[Don't bully.]  Words such as ``clearly'' and ``obviously'' serve
no logical function.  Rather, they almost always signal an attempt to
bully the reader into accepting something which the author is having
trouble justifying rigorously.  Don't use these words in your own
proofs and go on the alert whenever you read one.

\item[Finish.]  At some point in a proof, you'll have established all
the essential facts you need.  Resist the temptation to quit and leave
the reader to draw the right conclusions.  Instead, tie everything
together yourself and explain why the original claim follows.

\end{description}

The analogy between good proofs and good programs extends beyond
structure.  The same rigorous thinking needed for proofs is essential
in the design of critical computer system.  When algorithms and
protocols only ``mostly work'' due to reliance on hand-waving
arguments, the results can range from problematic to catastrophic.  An
early example was the Therac 25, a machine that provided radiation
therapy to cancer victims, but occasionally killed them with massive
overdoses due to a software race condition.  More recently, a buggy
electronic voting system credited presidential candidate Al Gore with
\textit{negative} 16,022 votes in one county.  In August 2004, a
single faulty command to a computer system used by United and American
Airlines grounded the entire fleet of both companies--- and all their
passengers.  

It is a certainty that we'll all one day be at the mercy of critical
computer systems designed by you and your classmates.  So we really
hope that you'll develop the ability to formulate rock-solid logical
arguments that a system actually does what you think it does.

\section{A Puzzle}

Here is a puzzle.  There are 15 numbered tiles and a blank square
arranged in a $4 \times 4$ grid.  Any numbered tile adjacent to the
blank square can be slid into the blank.  For example, a sequence of
two moves is illustrated below:

\[
\begin{array}{|c|c|c|c|}
\hline
1 & 2 & 3 & 4 \\ \hline
5 & 6 & 7 & 8 \\ \hline
9 & 10 & 11 & 12 \\ \hline
13 & 15 & 14 &  \\ \hline
\end{array}
\quad \rightarrow \quad
\begin{array}{|c|c|c|c|}
\hline
1 & 2 & 3 & 4 \\ \hline
5 & 6 & 7 & 8 \\ \hline
9 & 10 & 11 & 12 \\ \hline
13 & 15 &   & \mathbf{14} \\ \hline
\end{array}
\quad \rightarrow \quad
\begin{array}{|c|c|c|c|}
\hline
1 & 2 & 3 & 4 \\ \hline
5 & 6 & 7 & 8 \\ \hline
9 & 10 &   & 12 \\ \hline
13 & 15 & \mathbf{11} & 14 \\ \hline
\end{array}
\]

In the leftmost configuration shown above, the 14 and 15 tiles are out
of order.  Can you find a sequence of moves that puts these two
numbers in the correct order, but returns every other tile to its
original position?  Some experimentation suggests that the answer is
probably ``no'', so let's try to prove that.

We're going to take an approach that is frequently used in the
analysis of software and systems.  We'll look for an \term{invariant},
a property of the puzzle that is always maintained, no matter how you
move the tiles around.  If we can then show that putting the 14 and 15
tiles in the correct order would violate the invariant, then we can
conclude that this is impossible.

Let's see how this game plan plays out.  Here is the theorem we're
trying to prove:

\begin{theorem}
No sequence of moves transforms the board below on the left into the
board below on the right.
%
\[
\begin{array}{|c|c|c|c|}
\hline
1 & 2 & 3 & 4 \\ \hline
5 & 6 & 7 & 8 \\ \hline
9 & 10 & 11 & 12 \\ \hline
13 & \mathbf{15} & \mathbf{14} &  \\ \hline
\end{array}
\hspace{1in}
\begin{array}{|c|c|c|c|}
\hline
1 & 2 & 3 & 4 \\ \hline
5 & 6 & 7 & 8 \\ \hline
9 & 10 & 11 & 12 \\ \hline
13 & \mathbf{14} & \mathbf{15} &  \\ \hline
\end{array}
\]
\end{theorem}

\noindent We'll build up a sequence of observations, stated as lemmas.
Once we achieve a critical mass, we'll assemble these observations
into a complete proof.

Define a \term{row move} as a move in which a tile slides horizontally
and a \term{column move} as one in which a tile slides vertically.
Assume that tiles are read top-to-bottom and left-to-right like
English text; so when we say two tiles are ``out of order'', we mean
that the larger number precedes the smaller number in this order.

Our difficulty is that one pair of tiles (the 14 and 15) is out of
order initially.  An immediate observation is that row moves alone are
of little value in addressing this problem:

\begin{lemma}
\label{lem:row-move}
A row move does not change the order of the tiles.
\end{lemma}

\noindent Usually a lemma requires a proof.  However, in this case,
there are probably no more-compelling observations that we could use
as the basis for such an argument.  So we'll let this statement stand
on its own and turn to column moves.

\begin{lemma}
\label{lem:col-move}
A column move changes the relative order of exactly 3 pairs of tiles.
\end{lemma}

For example, the column move shown below changes the relative order of
the pairs $(j, g)$, $(j, h)$, and $(j, i)$.
%
\[
\begin{array}{|c|c|c|c|}
\hline
a & b & c & d \\ \hline
e & f &   & g \\ \hline
h & i & \mathbf{j} & k \\ \hline
l & m & n & o \\ \hline
\end{array}
\hspace{0.5in} \rightarrow \hspace{0.5in}
\begin{array}{|c|c|c|c|}
\hline
a & b & c & d \\ \hline
e & f & \mathbf{j} & g \\ \hline
h & i &   & k \\ \hline
l & m & n & o \\ \hline
\end{array}
\]

\begin{proof}
Sliding a tile down moves it after the next three tiles in the order.
Sliding a tile up moves it before the previous three tiles in the
order.  Either way, the relative order changes between the moved tile
and each of the three it crosses.
\end{proof}

These observations suggest that there are limitations on how tiles can
be swapped.  Some such limitation may lead to the invariant we need.
In order to reason about swaps more precisely, let's define a term: a
pair of tiles $i$ and $j$ is \term{inverted} if $i < j$, but $i$
appears after $j$ in the puzzle.  For example, in the puzzle below,
there are four inversions: (12, 11), (13, 11), (15, 11), and (15, 14).
%
\[
\begin{array}{|c|c|c|c|}
\hline
1 & 2 & 3 & 4 \\ \hline
5 & 6 & 7 & 8 \\ \hline
9 & 10 &   & 12 \\ \hline
13 & 15 & 11 & 14 \\ \hline
\end{array}
\]

Let's work out the effects of row and column moves in terms of
inversions.

\begin{lemma}
\label{lem:inversion-parity}
A row move never changes the parity of the number of inversions.  A
column move always changes the parity of the number of inversions.
\end{lemma}

The ``parity'' of a number refers to whether the number is even or
odd.  For example, 7 and -5 have odd parity, and 18 and 0 have even
parity.

\begin{proof}
By Lemma~\ref{lem:row-move}, a row move does not change the order of
the tiles; thus, in particular, a row move does not change the number
of inversions.

By Lemma~\ref{lem:col-move}, a column move changes the relative order
of exactly 3 pairs of tiles.  Thus, an inverted pair becomes
uninverted and vice versa.  Thus, one exchange flips the total number
of inversions to the opposite parity, a second exhange flips it back
to the original parity, and a third exchange flips it to the opposite
parity again.
\end{proof}

This lemma implies that we must make an \textit{odd} number of column
moves in order to exchange just one pair of tiles (14 and 15, say).
But this is problematic, because each column move also knocks the
blank square up or down one row.  So after an \textit{odd} number of
column moves, the blank can not possibly be back in the last row,
where it belongs!  Now we can bundle up all these observations and
state an invariant, a property of the puzzle that never changes, no
matter how you slide the tiles around.

\begin{lemma}
\label{lem:puzzle-invariant}
In every configuration reachable from the position shown below, the
parity of the number of inversions is different from the parity of the
row containing the blank square.
%
\[
\begin{array}{l}
\textit{row 1} \\
\textit{row 2} \\
\textit{row 3} \\
\textit{row 4} \\
\end{array}
\qquad
\begin{array}{|c|c|c|c|}
\hline
1 & 2 & 3 & 4 \\ \hline
5 & 6 & 7 & 8 \\ \hline
9 & 10 & 11 & 12 \\ \hline
13 & 15 & 14 &  \\ \hline
\end{array}
\]
\end{lemma}

\begin{proof}
We use induction.  Let $P(n)$ be the proposition that after $n$ moves,
the parity of the number of inversions is different from the parity of
the row containing the blank square.

\noindent \textit{Base case:} After zero moves, exactly one pair of
tiles is inverted (14 and 15), which is an odd number.  And the blank
square is in row 4, which is an even number.  Therefore, $P(0)$ is true.

\noindent \textit{Inductive step:} Now we must prove that $P(n)$
implies $P(n+1)$ for all $n \geq 0$.  So assume that $P(n)$ is true;
that is, after $n$ moves the parity of the number of inversions is
different from the parity of the row containing the blank square.
There are two cases:

\begin{enumerate}

\item Suppose move $n+1$ is a row move.  Then the parity of the total
number of inversions does not change by
Lemma~\ref{lem:inversion-parity}.  The parity of the row containing
the blank square does not change either, since the blank remains in
the same row.  Therefore, these two parities are different after $n+1$
moves as well, so $P(n+1)$ is true.

\item Suppose move $n+1$ is a column move.  Then the parity of the
total number of inversions changes by
Lemma~\ref{lem:inversion-parity}.  However, the parity of the row
containing the blank square also changes, since the blank moves up or
down one row.  Thus, the parities remain different after $n+1$ moves,
and so $P(n+1)$ is again true.

\end{enumerate}

\noindent Thus, $P(n)$ implies $P(n+1)$ for all $n \geq 0$.

By the principle of induction, $P(n)$ is true for all $n \geq 0$.
\end{proof}

The theorem we originally set out to prove is restated below.  With
this invariant in hand, the proof is simple.

\begin{theorem*}
No sequence of moves transforms the board below on the left into the
board below on the right.
%
\[
\begin{array}{|c|c|c|c|}
\hline
1 & 2 & 3 & 4 \\ \hline
5 & 6 & 7 & 8 \\ \hline
9 & 10 & 11 & 12 \\ \hline
13 & \mathbf{15} & \mathbf{14} &  \\ \hline
\end{array}
\hspace{1in}
\begin{array}{|c|c|c|c|}
\hline
1 & 2 & 3 & 4 \\ \hline
5 & 6 & 7 & 8 \\ \hline
9 & 10 & 11 & 12 \\ \hline
13 & \mathbf{14} & \mathbf{15} &  \\ \hline
\end{array}
\]
\end{theorem*}

\begin{proof}
In the target configuration on the right, the total number of
inversions is zero, which is even, and the blank square is in row 4,
which is also even.  Therefore, by Lemma~\ref{lem:puzzle-invariant},
the target configuartion is unreachable.
\end{proof}

If you ever played with Rubik's cube, you know that there is no way to
rotate a single corner, swap two corners, or flip a single edge.  All
these facts are provable with invariant arguments like the one above.
In the wider world, invariant arguments are used in the analysis of
complex protocols and systems.  For example, in analyzing the software
and physical dynamics a nuclear power plant, one might want to prove
an invariant to the effect that the core temperature never rises high
enough to cause a meltdown.

\section{Unstacking}

Here is another wildly fun 6.042 game that's surely about to sweep the
nation!  You begin with a stack of $n$ boxes.  Then you make a
sequence of moves.  In each move, you divide one stack of boxes into
two nonempty stacks.  The game ends when you have $n$ stacks, each
containing a single box.  You earn points for each move; in
particular, if you divide one stack of height $a + b$ into two stacks
with heights $a$ and $b$, then you score $ab$ points for that move.
Your overall score is the sum of the points that you earn for each
move.  What strategy should you use to maximize your total score?

As an example, suppose that we begin with a stack of $n = 10$ boxes.
Then the game might proceed as follows:

\[
\begin{array}{cccccccccccl}
\multicolumn{10}{c}{\text{stack heights}} & \quad & \text{score} \\
10&&&&&&&&& && \\
5&5&&&&&&&& && 25 \text{ points} \\
5&3&2&&&&&&& && 6 \\
4&3&2&1&&&&&& && 4 \\
2&3&2&1&2&&&&& && 4 \\
2&2&2&1&2&1&&&& && 2 \\
1&2&2&1&2&1&1&&& && 1 \\
1&1&2&1&2&1&1&1&& && 1 \\
1&1&1&1&2&1&1&1&1& && 1 \\
1&1&1&1&1&1&1&1&1&1 && 1 \\ \hline
\multicolumn{10}{r}{\text{total score}} & = & 45 \text{ points}
\end{array}
\]

Can you find a better strategy?

\subsection{Strong Induction}

We'll analyze the unstacking game using a variant of induction called
{\em strong induction}.  Strong induction and ordinary induction are
used for exactly the same thing: proving that a predicate $P(n)$ is
true for all $n \in \mathbb{N}$.

\textbox{
\textbf{Principle of Strong Induction. }  Let $P(n)$ be a predicate.  If

\begin{itemize}
\item $P(0)$ is true, and
\item for all $n \in \mathbb{N}$, $P(0)$, $P(1)$, \ldots, $P(n)$ imply $P(n+1)$,
\end{itemize}

then $P(n)$ is true for all $n \in \mathbb{N}$.
}

\noindent The only change from the ordinary induction principle is
that strong induction allows you to assume more stuff in the inductive
step of your proof!  In an ordinary induction argument, you assume
that $P(n)$ is true and try to prove that $P(n+1)$ is also true.  In a
strong induction argument, you may assume that $P(0)$, $P(1)$, \ldots,
$P(n-1)$, and $P(n)$ are \textit{all} true when you go to prove
$P(n+1)$.  These extra assumptions can only make your job easier.

Despite the name, strong induction is actually no more powerful than
ordinary induction.  In other words, any theorem that can be proved
with strong induction can also be proved with ordinary induction.
However, an apeal to the strong induction principle can make some
proofs a bit simpler.  On the other hand, if $P(n)$ is easily
sufficient to prove $P(n+1)$, then use ordinary induction for
simplicity.

\subsection{Analyzing the Game}

Let's use strong induction to analyze the unstacking game.  We'll
prove that your score is determined entirely by the number of boxes;
your strategy is irrelevant!

\begin{theorem}
Every way of unstacking $n$ blocks gives a score of $n(n-1)/2$ points.
\end{theorem}

There are a couple technical points to notice in the proof:

\begin{itemize}

\item The template for a strong induction proof is exactly the same as
for ordinary induction.

\item As with ordinary induction, we have some freedom to adjust
indices.  In this case, we prove $P(1)$ in the base case and prove
that $P(1), \ldots, P(n-1)$ imply $P(n)$ for all $n \geq 2$ in the
inductive step.

\end{itemize}

\begin{proof}
The proof is by strong induction.  Let $P(n)$ be the proposition that
every way of unstacking $n$ blocks gives a score of $n(n-1)/2$.

\noindent \textit{Base case:} If $n = 1$, then there is only one
block.  No moves are possible, and so the total score for the game is
$1(1 - 1)/2 = 0$.  Therefore, $P(1)$ is true.

\noindent \textit{Inductive step:} Now we must show that $P(1)$,
\ldots, $P(n-1)$ imply $P(n)$ for all $n \geq 2$.  So assume that
$P(1)$, \ldots, $P(n-1)$ are all true and that we have a stack of $n$
blocks.  The first move must split this stack into substacks with
sizes $k$ and $n-k$ for some $k$ strictly between 0 and $n$.  Now the
total score for the game is the sum of points for this first move plus
points obtained by unstacking the two resulting substacks:
%
\begin{align*}
\text{total score}
    & = \text{(score for 1st move)} \\
    & \quad + \text{(score for unstacking $k$ blocks)} \\
    & \quad + \text{(score for unstacking $n - k$ blocks)} \\
    & = k(n-k) + \frac{k(k-1)}{2} + \frac{(n-k)(n-k-1)}{2} \\
    & = \frac{2nk - 2k^2 + k^2 - k + n^2 - nk - n - nk + k^2 +k}{2} \\
    & = \frac{n(n-1)}{2}
\end{align*}
%
The second equation uses the assumptions $P(k)$ and $P(n-k)$ and the
rest is simplification.  This shows that $P(1)$, $P(2)$, \ldots,
$P(n)$ imply $P(n+1)$.

Therefore, the claim is true by strong induction.
\end{proof}
\end{document}

