\problemdata
{induction}
{Math Moose}

\begin{problem}
% ordinary induction
% source: fall98

The 6.042 mascot, Math Moose, made an amazing observation while
playing with his collection of unit squares over the weekend.

First, Math Moose put his favorite unit square down on the floor as in
diagram (a) of Figure~\ref{fig:squares}.  He noticed that the length of
the periphery of the resulting shape was 4, an even number.  Next, he
put a second unit square down next to the first so that the two
squares shared an edge as in diagram (b).  He noticed that the length
of the periphery of the resulting shape was now 6, which is also an
even number.  (The periphery of each shape in the figure is indicated
by a thicker line.)  
Math Moose continued to place squares so that
each new square shared an edge with at least one previously-placed
square and no squares overlapped.  Eventually, he arrived at the shape
in diagram (c).  He realized that the length of the periphery of this
shape was 36, which is again an even number.

Math Moose spent the rest of the weekend trying to create a shape with
an odd-length periphery, without any success.  Help him out by proving
by induction on the number of squares that the periphery length is
always even, no matter how many squares he places or how he arranges
them.

\begin{figure}[htbp]
\centerline{\psfig{figure=figures/ps2.eps,height=2.0in}}
\caption{Some of the shapes that Math Moose created.} \label{fig:squares}
\end{figure}

\solution{
  Let $P(n)$ be the predicate that the length of the periphery of
  shapes comprised of $n$ squares is even.  We prove $P(n)$ for all $n
  \geq 1$ by induction on $n$.  It is important to note that this
  predicate does not require the squares to be contiguous as discussed
  in the problem statement; that is, we have strengthened the
  predicate to include shapes comprised of a set of squares that are
  not necessarily contiguous.  In the case of such shapes, the length
  of the periphery denotes the sum of the length of the periphery of
  all sub-shapes.

  In the base case, $P(0)$ is true because the periphery of a shape
  comprised of $0$ squares has length $0$, which is even.

  In the inductive step, we must show that for all $n \geq 0$, if the
  length of the periphery of the shapes comprised of $n$ squares is
  even, then the length of the periphery of shapes comprised of $n+1$
  squares is even.  Consider any collection of shapes comprised of
  $n+1$ squares; call this collection of shapes $S'$.  Moreover, let
  $S$ denote collection of shapes obtained by removing an arbitrary
  square from $S'$; call this square $x$.  By the inductive
  hypothesis, we know that the length of the periphery of $S$ is even.
  Now, consider the effect on the length of the periphery of adding
  the square $x$ to the shape $S$ so as to get $S'$.  The square $x$
  shares either 0, 1, 2, 3, or 4 edges with the squares comprising
  $S$.  We analyze each of these cases separately:

  \begin{itemize}

  \item If the square $x$ shares no edges with any of the squares of
    $S$, then by adding the square $x$ the periphery length increases
    by four and thus remains even.

  \item If the square $x$ shares 1 edge with the squares of $S$, then
    this one edge is removed from the periphery, but three edges of
    the new square are added to the periphery.  Overall, the periphery
    length increases by two and thus remains even.

  \item If the square $x$ shares 2 edges with the squares of $S$, then
    these two edges are removed from the periphery, but two edges of
    the new square are added.  The periphery length is unchanged and
    thus remains even.

  \item If the square $x$ shares 3 edge with the squares of $S$, then
    these three edges are removed from the periphery, but one edge is
    added.  The periphery length decreases by two and remains even.

  \item If the square $x$ shares 4 edge with the squares of $S$, then
    these four edges are removed from the periphery and none are
    added.  The periphery length decreases by four and remains even.

  \end{itemize}

  In all cases, the length of the periphery remains even.  Therefore,
  for all $n \geq 1$, $P(n)$ implies $P(n+1)$.

  Thus, we have shown that the length of the periphery of any
  collection of shapes comprised of $n$ squares is even.  As a special
  case of what we have shown, it follows that the length of the
  periphery of a shape of $n$ contiguous squares build by Math Moose
  is also even.
}
\end{problem}