\problemdata
{induction}
{S00 ps2}

\begin{problem}
% ordinary induction 
% source: 
Suppose you take a piece of paper and draw a bunch of straight lines,
each in its own arbitrary direction, that completely cross the paper.
This divides the paper up into polygonal regions.  Prove by induction
that you can always color the various regions using only \emph{two}
colors, so that any two regions that share a boundary line are
different colors.  Note that this need not be true of regions that
share only a boundary point.

\solution{

  We assume that all lines are straight and completely cross the
  paper.  Also, when we say that the regions are colored, we always
  mean they are colored using at most two colors, \eg red and green.
  We say that two regions are \emph{adjacent} if they share a boundary
  line.  Note that two regions cannot share two distinct boundary
  lines.

  Let $P(n)$ be the predicate that the regions formed by any set of
  $n$ distinct lines can be colored so that (two) adjacent regions are
  colored with different colors.  We prove that $P(n)$ holds for all
  $n \in \mathbb{N}$ by induction on $n$.

\begin{description}

\item[Base case:] The base case is $P(0)$.  There is only one region,
  and thus there are no adjacent regions.  So this case is trivially
  true.  The region may be colored either red or green.

\item[Inductive step:] We must show that for all $n \in \nats$ it is
  the case that $(P(n) \implies P(n+1))$; that is, if the regions
  formed by any $n$ distinct lines can be colored so that adjacent
  regions have different colors, then the regions formed by any $n+1$
  distinct lines can be colored so that adjacent regions have
  different colors.

\begin{enumerate}

\item 
Fix $n \in \mathbb{N}$.

\item
Assume that the regions formed by any $n$ distinct lines 
can be colored so that adjacent regions have different colors. 

\item 
The regions formed by any $n+1$ distinct lines 
can be colored so that adjacent regions have different colors. 
\begin{enumerate}

\item
Fix a set of $n+1$ lines. 
These lines divide the paper into a set $X$ of regions. 

\item
Select any line $l$ from that set. 
There are $n$ other lines, 
which divide the paper into a set $Y$ of regions, 
such that every region in $X$ is either a region in $Y$ 
or else it is part of a region in $Y$ that is split by $l$. 

\item
By the inductive hypothesis, 
the regions in $Y$ can be colored 
so adjacent regions are different colors. 
This also gives a coloring for the regions in $X$. 
Call this coloring of the regions in $X$ the ``original coloring.''

\item Line $l$ splits the paper into two sides.  Select one of the
  sides and flip all the colors of the regions on that side.  Call
  this coloring of the regions in $X$ the ``new coloring.''  We prove
  that, using the new coloring, any adjacent regions in $X$ have
  different colors.
\begin{enumerate}

\item Fix any two adjacent regions in $X$.  
\begin{description}

\item[Case 1:\ ] The regions share boundary line $l$.  The two regions
  had the same color in the original coloring.  The two regions are on
  opposite sides of $l$.  Therefore, the color in exactly one of the
  two regions was flipped and they have different colors in the new
  coloring.

\item[Case 2:\ ] The regions do not share boundary line $l$.  The two
  regions had different colors in the original coloring, and they are
  on the same side of $l$.  Thus, the color of either none or both
  regions was flipped and the two regions have different colors in
  the new coloring.

\end{description}

\item QED (universal generalization over adjacent regions)

\end{enumerate}

\item QED (universal generalization over sets of $n+1$ lines)

\end{enumerate}

\item QED (implication)

\end{enumerate}

\item QED (induction)

\end{description}
}
\end{problem}
