\documentclass[11pt, twoside]{article}

\input{macros-course}
\usepackage{amsmath}

\newcommand{\nand}{|}
\renewcommand{\implies}{\longrightarrow}

\begin{document}
\psol{1}{February 8, 2000}

Solutions by Victor Luchangco and Joshua A.\ Tauber, 
with input from Robert Ragno and David Karger.

\begin{problems}
\problem In some computer architectures, the basic computer operation
is ``NAND'', denoted~$\nand$, where $A \nand B$ means $\neg (A \land
B)$.  Show that all the basic boolean operations can be implemented
using the single $\nand$ operation.  That is, rewrite each of the
following formulas as equivalent formulas using only the $\nand$
operator (and parentheses).

\begin{minipage}[t]{1.5in}
\begin{problemparts}
\ppart $\neg A$
\ppart $A \lor B$
\ppart $A \land B$
\ppart $A \implies B$
\end{problemparts}
\end{minipage}
\textbf{Solutions:}
\setcounter{problempartnum}{0}
\begin{minipage}[t]{3.5in}
\begin{problemparts}
\ppart $A \nand A$
\ppart $(A \nand A) \nand (B \nand B)$
        \quad ($\Longleftrightarrow
         \neg ( \neg A \land \neg B)
        \Longleftrightarrow 
        \neg A \nand \neg B$)
\ppart $(A \nand B) \nand (A \nand B)$ 
        \quad ($\Longleftrightarrow \neg(A \nand B)$)
\ppart $A \nand (B \nand B)$
        \quad ($\Longleftrightarrow B \lor \neg A)$)
\end{problemparts}
\end{minipage}


\problem Identify the premises and conclusions of the following
deductive arguments and analyze their logical forms.  This may require
that you ``pin down'' a statement that could be interpreted many ways.
Determine which are valid deductions and which are not.  If the
deduction is invalid, demonstrate a possible scenario in which all the
premises are met but the conclusion is not.

\textbf{Note:} There are several ways to formalize many of these statements in
logical notation.  We will accept any \emph{reasonable} reading of the English.
Below, we show one such solution for each part.

\begin{problemparts}
\ppart Jane and Pete won't both win the math prize.  Pete will win
either the math prize or the chemistry prize.  Jane will win the math
prize.  Thus, Pete will win the chemistry prize.

\textbf{Solution:} The deduction is:
\begin{center}
\begin{tabular}{l}
        $\neg (J \land M)$ \\
        $M \lor C$ \\ 
        $J$ \\ \hline
        $\therefore C$
\end{tabular}
\quad where 
\begin{tabular}{l}
        $J \equiv \mbox{``Jane will win the math prize.''}$ \\
        $M \equiv \mbox{``Pete will win the math prize.''}$ \\
        $C \equiv \mbox{``Pete will win the chemistry prize.''}$
\end{tabular}
\end{center}
This deduction is valid.  

\ppart The main course will be beef or fish.  The vegetable will be
peas or corn. We will not have both fish as a main course and corn as
a vegetable. Therefore, we will not have both beef as a main course
and peas as a vegetable.

\textbf{Solution:} The deduction is:
\begin{center}
\begin{tabular}{l}
        $B \lor F$ \\
        $C \lor P$ \\
        $\neg (F \land C)$ \\ \hline
        $\therefore \neg (B \land P)$
\end{tabular}
\quad where 
\begin{tabular}{l}
        $B \equiv \mbox{``The main course will be beef.''}$ \\
        $F \equiv \mbox{``The main course will be fish.''}$ \\
        $C \equiv \mbox{``The vegetable will be corn.''}$ \\
        $P \equiv \mbox{``The vegetable will be peas.''}$ 
\end{tabular}
\end{center}
This deduction is invalid.  For example, $B \land \neg F \land C \land
P$ is consistent with the premises but not with the conclusion.  Note
that as formalized, there need not be only one main course and only
one vegetable; it is possible, for example, for the vegetable to be
both corn and peas, as in the scenario given.  If we wished to exclude
the possibility of multiple courses we could have used exclusive-or
instead of inclusive-or. So our premise about the main course would
then read $B \oplus F$ or, equivalently, 
$(B \lor F) \land \neg (B \land F)$. 
The premise about the vegetable could be changed similarly.  
The deduction is still invalid with this formalization. 

\ppart Either John or Bill is telling the truth.  Either Sam or Bill
is lying.  Thus, either John is telling the truth or Sam is lying.

\textbf{Solution:}
We interpret ``John is lying,'' to be 
the negation of ``John is telling the truth.'' 
Similarly for the corresponding propositions involving Bill and Sam.
The deduction is:
\begin{center}
\begin{tabular}{l}
        $J \lor B$ \\
        $\neg S \lor \neg B$ \\ \hline
        $\therefore J \lor \neg S$
\end{tabular}
\quad where 
\begin{tabular}{l}
        $J \equiv \mbox{``John is telling the truth.''}$ \\
        $B \equiv \mbox{``Bill is telling the truth.''}$ \\
        $S \equiv \mbox{``Sam is telling the truth.''}$
\end{tabular}
\end{center}
This deduction is valid.  It is an example of a common
``cancellation'' rule that lets us get rid of the proposition $B$.

\ppart Either sales will go up and the boss will be happy, or expenses
will go up and the boss won't be happy.  Therefore, sales and expenses
will not both go up.

\textbf{Solution:} The deduction is:
\begin{center}
\begin{tabular}{l}
        $(S \land H) \lor (E \land \neg H)$ \\ \hline
        $\therefore \neg (S \land E)$
\end{tabular}
\quad where 
\begin{tabular}{l}
        $S \equiv \mbox{``Sales will go up.''}$ \\
        $H \equiv \mbox{``The boss will be happy.''}$ \\
        $E \equiv \mbox{``Expenses will go up.''}$ 
\end{tabular}
\end{center}
This deduction is invalid. 
For example, $S \land E \land H$ is consistent 
with the premises but not with the conclusion. 

\ppart If the tax rate and unemployment both go up then there will be
a recession.  If the GNP goes up there will not be a recession.  GNP
and taxes are both going up.  Therefore, there will not be a
recession.

\textbf{Solution:}
The deduction is:
\begin{center}
\begin{tabular}{l}
        $T \land U \implies R$ \\
        $G \implies \neg R$ \\
        $G \land T$ \\ \hline
        $\therefore \neg R$
\end{tabular}
\quad where 
\begin{tabular}{l}
        $T \equiv \mbox{``The tax rate goes up.''}$ \\
        $U \equiv \mbox{``Unemployment goes up.''}$ \\
        $G \equiv \mbox{``GNP goes up.''}$ \\
        $R \equiv \mbox{``There will be a recession.''}$
\end{tabular}
\end{center}
This deduction is valid. 
(The first premise is superfluous.)

\end{problemparts}

\problem Let $F(x,y)$ be the predicate ``$x$ can fool $y$'' and the
universe of discourse be the set of all people.  Use quantifiers to
express the following statements.
\begin{problemparts}
\ppart Everybody can fool Fred. \\
\textbf{Solution:}
$\forall x F(x,\textrm{Fred})$

\ppart Evelyn can fool everybody. \\
\textbf{Solution:}
$\forall y F(\textrm{Evelyn},y)$

\ppart Everybody can fool somebody. \\
\textbf{Solution:}
$\forall x \exists y F(x,y)$

\ppart No one can fool everybody. \\
\textbf{Solution:}
$\neg \exists x \forall y F(x,y)$

\ppart Everybody can be fooled by somebody. \\
\textbf{Solution:}
$\forall y \exists x F(x,y)$

\ppart Nancy can fool exactly two people. \\
\textbf{Solution:}
$\exists x \exists y 
    (x \neq y  
        \land F(\textrm{Nancy}, x)
        \land F(\textrm{Nancy}, y)
        \land \forall z 
                (z \neq x \land z \neq y \implies \neg F(\textrm{Nancy},z)))$
Alternatively: 
$\exists x \exists y 
    (x \neq y  
        \land F(\textrm{Nancy}, x)
        \land F(\textrm{Nancy}, y)
        \land \forall z 
                (z = x \lor z = y \lor \neg F(\textrm{Nancy},z)))$

Note that by convention, different logical operators bind more or less tightly.
Quantifiers and negation bind most tightly; 
$\land$ and $\lor$ bind more tightly than $\implies$.

\ppart There is exactly one person whom everybody can fool. \\
\textbf{Solution:}
$\exists! y \forall x F(x,y)$. 

Note that $\exists! y P(y)$ is logically equivalent to 
$\exists y (P(y) \land \forall z (z \neq y \implies \neg P(z)))$. 
Thus, it is possible to rewrite the statement as 
$\exists y (\forall x F(x,y) 
                \land \forall z (z \neq y \implies \neg \forall x F(x,z)))$. 

\ppart There is someone who can fool exactly one person besides him- or
herself. \\
\textbf{Solution:}
$\exists x \exists! y (x \neq y \land F(x,y))$.  
(This can be rewritten without $\exists!$ as we did above.)
%or $\exists y (x \neq y \land F(x,y) 
%               \land \forall z (z \neq y \implies \neg (x \neq z \land F(x,z))))$. 

\end{problemparts}


\problem Are these statements true or false?  The universe of
discourse is the natural numbers.  
(The set of natural numbers is $\{0,1,2, \ldots\}$.)

%\begin{minipage}[t]{3in}
\begin{problemparts}
\ppart $\forall x \exists y (2x-y=0)$

\textbf{Solution:}
True. (Given a natural number $x$, consider $y = 2x$; $y$ is a natural number.)
\ppart $\exists y \forall x (2x-y=0)$

\textbf{Solution:}
False. (Fix any $y$; there is always an $x > y/2$.)
\ppart $\forall x (x < 10 \implies \forall y (y < x \implies y < 9))$

\textbf{Solution:}
True.  (Remember the universe of discourse is the natural numbers.)
\ppart $\forall x \exists y (y > x \land \exists z (y+z=100))$

\textbf{Solution:} False. (If $x > 100$ then $y > 100$ so no $z \in \mathbb{N}$
works.)

\end{problemparts}

\problem \mbox{}
\begin{problemparts} 

\ppart
Show that $\forall x P(x) \lor \forall x Q(x)$ is not logically
equivalent to $\forall x (P(x) \lor Q(x))$.

\textbf{Solution:}
The universal quantifier does not distribute over OR.  
Even if $\forall x (P(x) \lor Q(x))$, 
there may be two elements, $c_1$ and $c_2$, such that 
$P(c_1) \land \neg Q(c_1) \land \neg P(c_2) \land Q(c_2)$, 
and thus, $\neg (\forall x P(x) \lor \forall x Q(x))$. 

For example, suppose the universe of discourse is $\mathbb{N}$,
$P(x)$ is the proposition ``$x$ is even,'' and $Q(x)$ is the
proposition ``$x$ is odd.''  
It is not true that every natural number is even 
(i.e., $\neg \forall x P(x)$), 
nor is it true that every natural number is odd 
(i.e., $\neg \forall x Q(x)$). 
However, every natural number is either even or odd 
(i.e., $\forall x (P(x) \lor Q(x))$). 

\ppart 
Show that $\exists x (P(x) \implies Q(x))$ is logically equivalent to
$\forall x P(x) \implies \exists x Q(x)$.

\textbf{Solution:}
First we show that the existential quantifier does distribute over OR:

\textbf{Lemma:} 
$\exists x (P(x) \lor Q(x))
                \Longleftrightarrow \exists x P(x) \lor \exists x Q(x)$. 

\textit{Proof:} 
In class, we showed one direction, 
that $\exists x (P(x) \lor Q(x))
                \Longrightarrow \exists x P(x) \lor \exists x Q(x)$. 
To see the other direction, 
suppose $\exists x P(x) \lor \exists x Q(x)$. 
We proceed by cases:
\begin{description}

\item[Case 1 ($\exists x P(x)$): ]
By existential instantiation, 
$P(c)$ for some $c \in U$. 
Therefore $P(c) \lor Q(c)$, 
and by existential generalization, 
$\exists x (P(x) \lor Q(x))$. 

\item[Case 2 ($\exists x Q(x)$): ]
This is exactly analogous to the previous case. 

\item[Exhaustive cases: ]
Since we have covered both disjuncts of our supposition, the two cases above are exhaustive.
\qed

\end{description}

We use this lemma in the following proof:
\begin{align*}
\exists x (P(x) \implies Q(x)) 
        & \Longleftrightarrow \exists x (\neg P(x) \lor Q(x)) 
                & \text{(truth table of $\implies$)} \\
        &\Longleftrightarrow \exists x \neg P(x) \lor \exists x Q(x) 
                & \text{(above lemma)} \\
        &\Longleftrightarrow \neg \forall x P(x) \lor \exists x Q(x) 
                & \text{(negation of $\forall$)} \\
        &\Longleftrightarrow \forall x P(x) \implies \exists x Q(x) 
                & \text{(truth table of $\implies$)} \\
\end{align*}

\end{problemparts}

\problem Consider the following theorem: Suppose $x$ is a real number
and $\frac{2x-5}{x-4}=3$ then $x=7$.
\begin{problemparts}
\ppart What is wrong with the following proof? Suppose $x=7$.  Then
\[
\frac{2x-5}{x-4}=\frac{2(7)-5}{7-4}=\frac{9}{3}=3.
\]
Thus, if $\frac{2x-5}{x-4}=3$ then $x=7$.

\textbf{Solution:} This proof is a typical example of circular
reasoning.  We suppose $x=7$ and then conclude that $x=7$.  So, all we
have done is not contradict our supposition.  Unlike a proof by
contradiction, which shows our assumption is false, {\em not} arriving
a contradiction does {\em not} show our assumption is true.

In particular, the proof is of the form:
\begin{center}
\begin{tabular}{l}
        $P(x)$ \\
        $P(x) \implies Q(x)$ \\ \hline
        $\therefore Q(x) \implies P(x)$
\end{tabular}
\quad where 
\begin{tabular}{l}
        $P(x) \;\; \equiv\;\; x=7$ \\
        $Q(x) \;\; \equiv\;\; \frac{2x-5}{x-4}=3$ \\
\end{tabular}
\end{center}
The given ``proof'' does demonstrate that the second premise is true.  
However, the conclusion does not follow.

\ppart Give a correct proof of this theorem.

\textbf{Solution:}
There are many ways to properly construct this proof.  We demonstrate a direct
proof using \emph{modus ponens}.

\begin{center}
\begin{tabular}{l}
        $Q(x)$ \\
        $Q(x) \implies P(x)$ \\ \hline
        $\therefore P(x)$
\end{tabular}
\quad where 
\begin{tabular}{l}
        $P(x) \;\; \equiv \;\; x=7$ \\
        $Q(x) \;\; \equiv \;\; \frac{2x-5}{x-4}=3$ \\
\end{tabular}
\end{center}
Proposition $Q(x)$ is given.  To complete the proof, we must now show that the
second premise (the implication) is a tautology.  
We do this using basic algebra and arithmetic:
\begin{align*}
Q(x) \equiv \frac{2x-5}{x-4} = 3 \;\;
        & \:\Longrightarrow \;\; 2x-5 = 3(x-4) \\ 
        & \Longleftrightarrow \;\; 2x-5 = 3x-12 \\
        & \Longleftrightarrow \;\; -5+12 = 3x-2x \\
        & \Longleftrightarrow \;\; 7 = x                &\equiv P(x) 
\end{align*}
\end{problemparts}



\problem Suppose $x$ is a real number.  Prove \textbf{by cases} that there is a
real $y$ such that $\frac{y+1}{y-2}=x$ if and only if $x \ne 1$.

\textbf{Solution:}
We consider the cases $x \neq 1$ and $x = 1$ separately. 
\begin{description}

\item[Case 1 ($x \not = 1$): ]
We need to prove that there exists $y \in \mathbb{R}$ such that
$\frac{y+1}{y-2}=x$.  In particular, consider $y = \frac{2x+1}{x-1}$ (derived
by algebraic manipulation), which is a well-defined real number because $x \neq
1$.  Then:  
\[\frac{y+1}{y-2} 
        = \frac{\frac{2x+1}{x-1}+1}{\;\frac{2x+1}{x-1}-2\;} 
        = \frac{\frac{2x+1 + (x-1)}{x-1}}{\;\frac{2x+1-2(x-1)}{x-1}\;}
        = \frac{\frac{3x}{x-1}}{\;\frac{2x+1-2x+2}{x-1}\;}
        = \frac{3x}{3}
        = x
\]
Therefore, by existential generalization, $\exists y \in \mathbb{R}$ such that
$\frac{y+1}{y-2} = x.$

\item[Case 2 ($x = 1$): ]
We need to prove that no $y \in \mathbb{R}$ exists 
such that $\frac{y+1}{y-2}=x$. 
Suppose, for contradiction, that such a $y$ did exist.  Then:
\begin{align*}
\frac{y+1}{y-2} = x 
        &\Longleftrightarrow \;\; \frac{y+1}{y-2} = 1 
                & \text{(because $x = 1$)} \\
        &\:\Longrightarrow \;\; y+1 = y-2 
                & \text{(multiply both sides by $y-2$)} \\
        &\Longleftrightarrow \;\; 1 = -2 
                & \text{(subtract $y$ from both sides)} \\
        &\Longleftrightarrow \;\; \text{false.}
\end{align*}
Therefore our supposition is wrong, 
and there is no $y$ such that $\frac{y+1}{y-2}=x$. 

\end{description}

\problem Consider the following incorrect theorem:  
\[\text{If } \forall x \in A \; (x \ne 0) \text{ and }A \subseteq B \text{ then
}\forall x \in B \; (x \ne 0)\text{.}\] 

\vspace{-3ex}
\begin{problemparts}
\ppart What is wrong with the following proof of the theorem? Let $x$
be an arbitrary element of $A$.  Since $\forall x \in A \; (x \ne 0)$ we can
conclude $x \ne 0$.  Also, since $A \subseteq B$ we have $x \in B$.
Since $x \in B$, $x \ne 0$, and $x $ was arbitrary, we can conclude
(by universal generalization) that $\forall x \in B \; (x \ne 0)$.

\textbf{Solution:}
Universal generalization requires that the generalized variable be
arbitrarily chosen \emph{from the set over which we are
generalizing}. We selected $x$ arbitrarily from set $A$ but are
generalizing over a different (larger) set $B$, 
which is not a valid inference rule.   To use universal generalization,
we should imagine an adversary picking the worst possible element from
the set over which we are generalizing.  The proof must work even for that
worst case.

\ppart Give a counterexample to the theorem.

\textbf{Solution:} 
Let $A = \mathbb{N^+}$ and $B = \mathbb{Z}$. 

\end{problemparts}


\problem
Find a closed-form formula for 
\[
\frac{1}{1*2} + \frac{1}{2*3} + \frac{1}{3*4} + \ldots + \frac{1}{n(n+1)}
\]
by examining the values of this expression for small values of $n$.
Use mathematical induction to prove your formula holds for all natural
numbers.

\textbf{Solution:}
Let $s(n) = \frac{1}{1*2} + \frac{1}{2*3} + \frac{1}{3*4} + \ldots + \frac{1}{n(n+1)}$. 
For small values of $n$, we have:
\begin{center}
\begin{tabular}{l|c}
$n$ & $s(n)$ \\
\hline
$0$ & $0$ \\
$1$ & $1/2$ \\
$2$ & $2/3$ \\
$3$ & $3/4$ 
\end{tabular}
\end{center}
So we guess that $s(n) = n/(n+1)$. 

Let $P(n)$ be the proposition that $s(n) =  n/(n+1)$.
We want to prove, by induction, $\forall n \in \mathbb{N}\;P(n)$.

\begin{enumerate}

\item (Base case: Prove $P(0)$.)  The base case is established by the table
above. 

\item (Inductive case: Prove $\forall n \in \mathbb{N}\;(P(n) \implies
P(n+1))$.) Substituting our definition of $P(n)$, we must show 
$s(n) = \frac{n}{n+1} \implies s(n+1) = \frac{n+1}{n+2}$ 
for all natural numbers $n$.  
\begin{tabbing}
XXXXXXti\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
 1. Fix $n \geq 0$.\\
 2. Assume $s(n)= \frac{n}{n+1}$\\ 
 3. $s(n+1)$ 
\>  $ = s(n) +  \frac{1}{(n+1)(n+2)}$
  \>   (definition of $s(n)$) \\[.5ex] 

\>  $=\frac{n}{n+1}+\frac{1}{(n+1)(n+2)}$
  \>  (inductive hypothesis) \\[.5ex]  
\>  $=\frac{(n+1)^2}{(n+1)(n +2)}$            
  \>  (algebra)\\[.5ex]   
\>  $=\frac{(n+1)}{(n+2)}$
  \>  (division, note: $n+1 \not = 0$)\\ 
 4. QED 
\>\>  (implication)
\end{tabbing}

\item QED (induction)
\end{enumerate}

\end{problems}

\end{document}


%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% End of document %%%%
%%%%%%%%%%%%%%%%%%%%%%%%%

\problem 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.

\textbf{Solution 1:}
For this 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 only [[[at most?]]] two colors, 
red and green. 
[[[Is it better to just say ``using two colors'' everywhere?]]]
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 proposition that the regions formed by 
any set of $n$ distinct lines can be colored 
so that (two) adjacent regions are different colors. 
We prove $\forall n \in \mathbb{N} \; P(n)$ by induction (on $n$). 

\begin{description}

\item[Base case: $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: $\forall n \in \mathbb{N}\;(P(n) \implies P(n+1))$. ]
We must show that 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:\ ]They 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:\ ]They 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}

\textbf{Solution 2:}
We say a piece of paper divided into regions is 2-colorable if the regions can
be colored using only two colors so that any two regions that share a boundary
line are different colors.

Let $P(n)$ be the proposition that a piece of paper with any $n$ straight,
completely-crossing lines is 2-colorable. We want to prove, by induction on the
number of lines, $\forall n \in \mathbb{N}\;P(n)$. 

(For the purposes of this proof, we assume all lines are distinct, straight,
and completely cross the paper.)

\begin{enumerate}
\item (Base case: Prove $P(0)$.)  Select one of your colors; color the entire
piece of paper with it. Note that there are no two regions that share a
boundary line therefore this satisfies the condition trivially.

\item (Inductive case: Prove $\forall n \in \mathbb{N}\;(P(n) \implies
P(n+1))$.) Substituting our definition of $P(n)$, we must show that if a paper
divided up by any $n$ lines is 2-colorable then a paper divided up by $n+1$
lines is 2-colorable, for all natural numbers $n$.
\begin{enumerate}
\item Fix $n \geq 0$.
\item Assume a piece of paper divided up by any $n$ lines is 2-colorable.
\item A piece of paper divided by $n+1$ lines is 2-colorable.
\begin{enumerate}
\item Fix a piece of paper with $n+1$ lines.
\item Select any line $l$ on the page. Consider the piece of paper as divided
by the other $n$ lines.  By the inductive  hypothesis, the $n$-line page is
2-colorable. 
\item  Line $l$ divides the paper into two sides.  Select one of the sides and
flip the colors of all the regions on that side. The piece of paper with
$n+1$ lines is now 2-colored.
\begin{enumerate}
\item Consider any two regions that share a boundary line. They are different
colors.
\begin{description}
\item[Case 1:\ ]The boundary line is part of $l$. The two regions had the same
color on the $n$-line page.  The two regions are on opposite sides of $l$.
Therefore, the color in exactly one of the two regions was flipped.
\item[Case 2:\ ]The boundary line is not part of $l$. The two regions had
different colors on the $n$-line page.  The two regions are on the
same side of $l$.  Therefore, the color of either none or both regions was
flipped.
\item QED (cases)
\end{description}
\item QED (universal generalization over the regions)
\end{enumerate}
\item QED (universal generalization over pieces of paper with $n+1$ lines)
\end{enumerate}
\item QED (Implication)
\end{enumerate}
\item QED (Induction)
\end{enumerate}


\end{problems}


