\documentclass[11pt, twoside]{article}

\usepackage{psfig}

\input{macros-course}

\newtheorem*{corollary*}{Corollary}

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

\renewcommand{\problem}{\stepcounter{problemnum}\paragraph{\theproblem}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Printing the page layout parameters

\printlayout

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

\typein[\answer]{Include solutions? (y/n) }
\def\yes{y}
\ifx\answer\yes
  \typeout{}
  \typeout{Solutions *INCLUDED*.} 
  \newcommand{\reading}[1]{}
  \newcommand{\omitsolution}[1]{#1}
%  \usepackage[dark,first,bottom]{draftcopy}
%  \draftcopyName{Solutions}{155}
%
  \newcommand{\handoutlabel}{ps2sols}
  \newcommand{\handouttitle}{Problem Set 2 Solutions}
  \newcommand{\handoutdate}{February 15, 2000}
  \newcommand{\collaboration}{}
%
\else 
  \typeout{}
  \typeout{Solutions *NOT INCLUDED*.} 
  \newcommand{\reading}[1]{#1\vfill\mbox{}\newpage}
  \newcommand{\omitsolution}[1]{}
%
  \newcommand{\handoutlabel}{ps2}
  \newcommand{\handouttitle}{Problem Set 2}
  \newcommand{\handoutdate}{February 8, 2000}
  \newcommand{\collaboration}{\collaborationnote}
%
\fi

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

\begin{document}

\handout{\handoutlabel}{\handouttitle}{\handoutdate}

\reading{%

\textbf{Self-Study Reading:}%
\vspace*{-0.5\baselineskip}
\begin{description}\itemsep 0\baselineskip
\item[Rosen, \textit{Discrete Mathematics and Its Applications}:] \mbox{} \\ %
Sections 1.4, 1.5, 1.6
\item[Velleman, \textit{How to Prove It}:] \mbox{} \\ %
Sections 1.3, 1.4, 2.3
\end{description}

\textbf{Note:} The self-study reading covers basic mathematical topics
that we assume you are familiar with and that will not be explicitly
covered in the lectures.  We recommend that you skim them over and
encourage you to discuss any topics that are unclear to you with your
TA during the weekly tutorial.

\bigskip

\hrule
\vspace*{0.5\baselineskip}

\textbf{Self-Study Problems:}%
\vspace*{-0.5\baselineskip}
\begin{description}\itemsep 0\baselineskip
\item[Rosen, \textit{Discrete Mathematics and Its Applications}:] \mbox{} \\ %
  Section 1.4, exercises 5, 7, 9, 13, 17, 23 \\
  Section 1.5, exercises 3, 7, 15, 17, 19, 21 \\
  Section 1.6, exercises 1, 7, 10, 11, 13, 15, 17
\item[Velleman, \textit{How to Prove It}:] \mbox{} \\ %
  Section 1.4, exercises 1, 3, 8 \\
  Section 2.3, exercises 3, 6, 7
\end{description}

\textbf{Note:} The self-study problems are intended for you to get
some practice on the mathematical topics covered by the self-study
reading.  Again, make sure that you understand the concepts presented
in the problems and that you discuss any topics that are unclear to
you with your TA during the weekly tutorial.

\bigskip

\hrule
\vspace*{0.5\baselineskip}

\textbf{Reading:}
\vspace*{-0.5\baselineskip}
\begin{description}\itemsep 0\baselineskip
\item[Rosen, \textit{Discrete Mathematics and Its Applications}:] \mbox{} \\ %
Induction: Sections 3.2, 3.3 \\
Relations: Section 6.1
\item[Velleman, \textit{How to Prove It}:] \mbox{} \\ %
Induction: Sections 6.1--6.4 \\
Relations: Sections 4.1--4.2 
\end{description}

}

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

\collaboration

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

%\begin{problems}

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

\omitsolution{%
\begin{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{solution}
}

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

\problem
% ordinary induction
% source:  Parmenter p. 173

Prove by induction that $\forall\; n \geq 1$, the quantity $n^3 +
(n+1)^3 + (n+2)^3$ is divisible by~$9$.

\omitsolution{%
\begin{solution}
  Let $P(n)$ be the predicate that $n^3 + (n+1)^3 + (n+2)^3$ is
  divisible by $9$, \ie $P(n) = 9 | (n^3 + (n+1)^3 + (n+2)^3)$.  We
  prove that $P(n)$ holds for all $n \geq 1$ by induction on $n$.  In
  fact, the predicate $P(n)$ is also true for $n = 0$.

  \begin{description}\itemsep 0\baselineskip
  \item[Base Case:~~] $P(1)$ \mbox{} \\
    $P(1) = 9 | (1^3 + 2^3 + 3^3) = 9 | 36 = \True$ 

  \item[Inductive Step:~~] For all $n \geq 1$, $P(n) \implies P(n+1)$
    \begin{enumerate}\itemsep 0ex
    \item Fix $n \geq 1$.

    \item From the inductive hypothesis $P(n)$ holds, \ie $9 | (n^3 +
      (n+1)^3 + (n+2)^3)$.

    \item We must show that $P(n+1)$ holds, \ie $9 | ((n+1)^3 +
      (n+2)^3 + (n+3)^3)$.
          
      \begin{enumerate}\itemsep 0ex
      \item $(n+1)^3 + (n+2)^3 + (n+3)^3 = n^3 + (n+1)^3 + (n+2)^3 + 9
        (n^2 + 3n +3)$
        
      \item From the inductive hypothesis, $9 | (n^3 + (n+1)^3 + (n+2)^3)$.
        
      \item Also, it is simple to see that $9 | (9 (n^2 + 3n +3))$.

      \item Since $9$ divided both terms, it divides their sum.

      \item QED
          
      \end{enumerate}

    \item QED (implication and UG)

    \end{enumerate}

  \end{description}

\end{solution}
}

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

\problem 
% ordinary induction
% source: fall98

Prove by induction on $n$ that for all $n \geq 0$, the inequality $|x|
+ |y| \leq n$ has exactly $2 n^2 + 2n + 1$ solutions where $x$ and $y$
are integers.

\omitsolution{%
\begin{solution}
  Let $P(n)$ be the proposition that there are $2 n^2 + 2n + 1$
  solutions to the inequality $|x| + |y| \leq n$, where $x$ and $y$
  are integers.  We prove that $P(n)$ holds for all $n \geq 0$ by
  induction on~$n$.

  In the base case, $P(0)$ is true because $2 (0)^2 + 2 (0) + 1 = 1$
  and there is one solution to the equation $|x| + |y| \leq 0$, namely
  $x = y = 0$.  This is easily argued by contradiction.  Without loss
  of generality, suppose that $x$ is not zero.  Then, since $|z| \geq
  0$, for all $z$, and $|z| > 0$, for all $z \not = 0$, it follows
  that $|x| + |y| > 0$; a contradiction.  Thus, $x$ must be zero.

  In the inductive step, assume $P(n)$ to prove $P(n+1)$.  That is, we
  want to prove that there are $2 (n+1)^2 + 2 (n + 1) + 1 = 2n^2 + 6n
  + 5$ solutions to the inequality $|x| + |y| \leq n + 1$.  Every
  solution to this inequality is also either a solution to the tighter
  inequality $|x| + |y| \leq n$ or else to the equation $|x| + |y| = n
  + 1$.  Thus, the number of solutions is equal to the number of
  solutions to the tighter inequality plus the number of solutions to
  the equation.

  By the inductive hypothesis, there are $2 n^2 + 2n + 1$ solutions to
  the tighter inequality.  All that remains is to count solutions to
  the equation.  The value of $x$ must be in the range $-(n+1),
  \ldots, n+1$.  If $x$ takes on either of the two values $-(n+1)$ or
  $n+1$, then there is a single solution, with $y = 0$.  If $x$ takes
  on one of the $2n+1$ values in the range $-n, \ldots, n$, then there
  are two solutions, one with $y = n + 1 - |x|$ and one with $y = -(n
  + 1 - |x|)$.  Thus, there are $2 + 2 \cdot (2n + 1) = 4n + 4$
  solutions to the equation and $2 n^2 + 2n + 1$ solutions to the
  tighter inequality, giving $2 n^2 + 6n + 5$ solutions in all, as
  desired.  Therefore, $P(n)$ implies $P(n+1)$, which concludes the
  inductive step.
\end{solution}
}

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

\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}

\omitsolution{%
\begin{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{solution}
}

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

\problem
% strengthen inductive hypothesis
% source:  fall96

The C.I.A. wants you to design plans to build, for an arbitrary $k
\geq 1$, a $2^k \times 2^k \times 2^k$ cubic foot granite cube that is
solid except for a missing single cubic foot that is one of the eight
cubic feet nearest the center of the cube.  It will have one of its
corners exactly at the center of the large cube.  The C.I.A. is not
telling you what is to be placed inside the cube.

You are to build this by cementing together {\em basic blocks} that
are 2-foot $\times$ 2-foot $\times$ 2-foot cubes, with one one-foot
cube missing from its corner~---~as shown in the diagram below.

\begin{figure}[h]
\centerline{\psfig{figure=figures/cube.ps,height=1in}}
\end{figure}

Describe your method for doing this.  Your plans should be described
recursively on $k$.

\omitsolution{
  \begin{solution}
    Let an $2^n \times 2^n \times 2^n$ cube with an arbitrary one-foot
    cubic block missing be denoted as an $n$-cube.  Moreover,
    throughout this problem, we assume that the one-foot block that is
    missing from any $n$-cube is at a lattice point, \ie at an
    integral number of feet from each side.

    \begin{theorem*} 
      For any positive integer $n$, any $n$-cube can be build out of
      $1$-cubes.
    \end{theorem*}
    \begin{proof} 
      Let $P(n)$ be the predicate that an $n$-cube can be build out of
      $1$-cubes.  We prove that $P(n)$ holds for any positive integer
      $n$ by induction on $n$.
      
      \begin{description}\itemsep 0ex
      \item[Base Case:~~] $P(1)$ is true since a $1$-cube is what we
        need to build.  This is precisely what we are given as a basic
        block.
 
      \item[Inductive Step:~~] We must show that for any positive
        integer $n$, $P(n)$ implies $P(n+1)$.  Consider an
        $(n+1)$-cube.  This block can be built using eight $n$-cubes
        as follows: build seven $n$-cubes such that they are all
        missing one of their corner blocks, arrange them so that their
        missing corner blocks meet in the center of the $(n+1)$-cube,
        fill up the gap with a $1$-cube such that the corner
        corresponding to the eighth $n$-cube is left empty, and,
        finally, build the eighth $n$-cube such that the appropriate
        one-foot cubic block is missing.  Notice, that the eight
        $n$-cubes can be build as desired because of the inductive
        hypothesis; that is, that any $n$-cube can be build out of
        $1$-cubes.
      \end{description}
    \end{proof}

    Now, we can state the following corollary.

    \begin{corollary*}
      For any positive integer $n$, an $n$-cube with any one-foot
      cubic block missing from its center can be build out of
      $1$-cubes.
    \end{corollary*}
    \begin{proof}
      $n$-cubes of this particular form, \ie with any one-foot cubic
      block missing from their center, is a particular case of what we
      showed in the above Theorem.  Thus, we know that $n$-cube with
      any one-foot cubic block missing from its center can be build
      out of $1$-cubes.  The construction of such a block can be done
      as outlined in the above theorem, with the exception that the
      missing one-foot block is missing from the center of the
      $(n+1)$-cube.
    \end{proof}
  \end{solution}
  }

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

\problem
% multi base cases, strong induction

One plan considered by the 6.042 staff, then dropped, involved
requiring students in tutorials to work in groups of either exactly 4
or exactly 7 students. 
We abandoned this plan when we realized that a tutorial section of
size 13 could not be split up in this way.

\bparts 

\ppart What is the smallest number $k$ such that all tutorials of $k$
or more students \emph{can} be split into teams of 4 and 7?

\ppart Prove that $k$ is the smallest such number.

\ppart Prove (by induction) that all tutorials of $k$ or more students
can be split into teams of size 4 and 7.

\eparts

\omitsolution{%
  \begin{solution}
  \bparts 

  \ppart The smallest number $k$ such that all tutorials of $k$ or
  more students \emph{can} be split into teams of 4 and 7 is $18$.

  \ppart A tutorial of size $17$ \emph{can not} be split into teams of
  4 and 7.  In particular, a tutorial of size $17$ can contain at most
  2 groups of 7.  Consider the various possible splits of the
  tutorial: i) no groups of 7: since the only other group size is 4 we
  can not split the tutorial of 17; ii) one group of 7: the remaining
  10 students can not be split into groups of 4; iii) two groups of 7:
  the remaining 3 students can not be split into groups of 7.

  \ppart The proof is by strong induction on the size $n$ of the
  tutorial.  Let $P(n)$ be the predicate that a tutorial of size $n$
  can be split into groups of size 4 and 7.

  We must show that $P(n)$ holds for all $n \geq 18$.

  \begin{tabbing}
    XXX\=XXX\=XXX\=XXX\=XXX\=XXX\=XXX\=XXX\=XXX\=XXX\=XXX\=\kill
    1. \textbf{Base Case:} $P(18)$, 18 = 4 + 7 + 7 \\
    2. \textbf{Base Case:} $P(19)$, 19 = 4 + 4 + 4 + 7 \\
    3. \textbf{Base Case:} $P(20)$, 20 = 4 + 4 + 4 + 4 + 4 \\
    4. \textbf{Base Case:} $P(21)$, 21 = 7 + 7 + 7 \\
    5. \textbf{Inductive Step:} 
    $\forall\; n \geq 21, ( \forall\; k \in [18,n], P(k) ) \implies P(n+1)$ \\
    \> 1. Fix $n \geq 21$.\\
    \> 2. From the inductive hypothesis $P(k)$ holds, for all $k \in [18,n]$. \\
    \> 3. In particular, $P(n-3)$ holds. \\
    \> 4. The size of the $n+1$ student tutorial is $4$ students
    greater than the $n-3$ student tutorial. \\
    \> 5. Thus, we can split up the $n+1$ tutorial as the $n-3$ tutorial \\
    \> \quad\ and with an extra 4 student group. \\
    \> 6. QED \\
    6. QED                        
  \end{tabbing}

  \eparts
  \end{solution}
}

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

\problem
% strong induction
% source: Velleman section 6.4, problem 9

Let the sequence $G_0, G_1, G_2,\ldots$ be defined recursively as
follows: $G_0 = 0$, $G_1 = 1$, and $G_n = 5 G_{n-1} - 6 G_{n-2}$, for
every $n \in \mathbb{N}, n \geq 2$.

Prove that for all $n \in \mathbb{N}$, $G_n = 3^n - 2^n$.

\omitsolution{%
\begin{solution}
  Let $P(n)$ be the predicate that $G_n = 3^n - 2^n$.  We prove
  $P(n)$, for all $n \in \mathbb{N}$, by strong induction on $n$.

  \begin{description}\itemsep 0\baselineskip
  \item[Base Case:] \mbox{} \\ In order to simplify the strong
    induction, we use two base cases, in particular $n = 0$ and $n =
    1$.  By the definition of the sequence it is the case that $G_0 =
    0$.  For $n = 0$, it is the case that $3^n - 2^n = 3^0 - 2^0 = 1 -
    1 = 0$; that is, it follows that $P(0)$ holds.  Similarly, by the
    definition of the sequence it is the case that $G_1 = 1$.  For $n
    = 1$, it is the case that $3^n - 2^n = 3^1 - 2^1 = 3 - 2 = 1$;
    that is, it follows that $P(1)$ holds.

  \item[Inductive Step:] \mbox{} \\ %
    We must show that for all $n \in \nats, n \geq 2$, it is the case
    that $(\forall\; k \in [ 0, n ], P(k)) \implies P(n+1)$.
    
    \begin{enumerate}\itemsep 0\baselineskip
    \item Fix $n \in \nats, n \geq 2$.
      
    \item Assume that the elements of the sequence $G_x$, for $0 \leq
      x \leq n$, can be expressed as $G_x = 3^x - 2^x$.
      
    \item The element of the sequence $G_{n+1}$ can be expressed as
      $G_{n+1} = 3^{n+1} - 2^{n+1}$.
      
      \begin{enumerate}\itemsep 0\baselineskip
      \item By the definition of the sequence we have $G_{n+1} = 5 G_n
        - 6 G_{n-1}$.  
        
      \item By our induction hypothesis, it is the case that $G_n =
        3^n - 2^n$ and $G_{n-1} = 3^{n-1} - 2^{n-1}$
        
      \item Thus, $G_{n+1} = 5 (3^n - 2^n) - 6 (3^{n-1} - 2^{n-1})$.
        Working through the algebra, we conclude that $G_{n+1} =
        3^{n+1} - 2^{n+1}$, as needed for the inductive step.
        
      \item QED 
        
      \end{enumerate}
      
    \item QED (implication and UG)
      
    \end{enumerate}
    
  \item QED (induction)
    
  \end{description}

\end{solution}
}

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

\problem
% tournaments?

Construct the following rankings for $n$-player tournaments, for any
$n \geq 2$, or show that this is not always possible.

\bparts 

\ppart Assume that one player, Enrique, wins all his matches, and
another, Ricky, wins all but one of his matches.  Construct a ranking
that is locally fair, and in which Enrique is first and Ricky second.

\ppart Assume that there are no sets of 3 players, A, B, and C, such
that A beats B, B beats C, and C beats A; that is, $\nexists A, B, C,
[(A \text{ beats } B) \wedge (B \text{ beats } C) \wedge (C \text{
  beats } A)]$.  Construct a ranking that is extremely fair, in the
sense that any player X that beats another player Y appears higher
than Y in the rankings.

\eparts

\omitsolution{%
\begin{solution}
  \bparts

  \ppart Since Enrique beat everyone and Ricky beat everyone but one
  person, it follows that Ricky lost to Enrique.  Now, consider all
  the other players in the tournament.  As seen in class, they can be
  ordered in a locally-fair ranking.  It follows that a locally-fair
  ranking for all the players is the ranking with Enrique first, Ricky
  second, and the remaining players ranked based on a locally-fair
  ranking.  We know that Enrique beat Ricky, that Ricky beat the
  player ranked third since he beat everyone but Enrique, and that the
  remaining players are ranked in a locally-fair fashion.

  \ppart \mbox{} \\
  \begin{theorem*}
    In any tournament with no 3-player cycles, a locally-fair ranking
    is extremely fair.
  \end{theorem*}
  \begin{proof}
    First, consider the case when there is only one or two players.
    In the case of one player, the ranking is trivial.  In the case of
    two players, an extremely fair ranking can be constructed by
    placing the winner first and the loser second.  Now consider a
    tournament of at least 3 players, in which there are no 3-player
    cycles.  In class we have shown that if a tournament has a cycle,
    then the tournament has a 3-player cycle.  Thus, the
    contrapositive is also true; that is, if a tournament has no
    3-player cycle, then the tournament has no cycles.  

    Consider a locally-fair ranking of a tournament with no 3-player
    cycles.  We show that the locally-fair ranking is extremely fair
    by contradiction.  Assume that the locally-fair ranking is not
    extremely fair.  Since the ranking is not extremely fair, there
    exist players $X$ and $Y$ such that $X$ appears higher in the
    ranking than $Y$ even though $Y$ beat $X$, \ie $\cdots X
    \rightarrow \cdots \rightarrow Y \cdots$ and $Y \rightarrow X$.
    It follows that the tournament graph contains the cycle $X
    \rightarrow \cdots \rightarrow Y \rightarrow X$.  Since it
    contains a cycle, it must also contain a 3-player cycle.  This
    contradicts the fact that the tournament has no 3-player cycles.
    It follows that our assumption that the ranking is not extremely
    fair is false.
  \end{proof}
 
  \eparts
\end{solution}
}

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

\problem
% structural induction 

The set $W$ of ``well-formed parenthesis strings'' can be defined by
the following rules:

\vspace*{-0.5\baselineskip}

\begin{enumerate}\itemsep 0\baselineskip
\item the empty string is in $W$, and
\item if $s$ and $t$ are in W then the string $(s)t$ is in $W$.
\end{enumerate}
For example, the string $(()())()$ is a well-formed parenthesis
string, where as the string $)(())$, isn't.

Use structural induction to prove that any prefix of any well-formed
parenthesis string has at least as many left parentheses as right
parentheses.

\omitsolution{%
\begin{solution}
  Let $P(t)$, for $t \in W$, be the predicate that any prefix of a
  well-formed parenthesis string $t$ has at least as many left as
  right parentheses.  We prove that $P(t)$ holds for all $t \in W$ by
  structural induction.

  \begin{description}\itemsep 0\baselineskip
  \item[Base Case:] \mbox{} \\ %
    Let $t$ be the empty string $\lambda$.  $P(\lambda)$ holds since
    there are no left or right parentheses.

  \item[Inductive Step:] \mbox{} \\ %
    We must show that for all $s, t \in W$, $P(s)$ and $P(t)$ imply
    $P((s)t)$; that is, that any prefix of the string $(s)t$ has at
    least as many left as right parentheses.  Let $s, t$ be any
    strings in $W$ and assume that $P(s)$ and $P(t)$ hold.  Moreover,
    for any $s_1$ and $s_2$, let $s_1 \leq s_2$ denote that $s_1$ is a
    prefix of the string $s_2$.  Let $p$ be any prefix of the string
    $(s)t$ and consider the following set of exhaustive cases:

    \begin{description}\itemsep 0\baselineskip
    \item[$p = \lambda$] \mbox{} \\ %
      In this case, $p$ trivially satisfies the claim.

    \item[$p = ($] \mbox{} \\ %
      In this case, $p$ trivially satisfies the claim.

    \item[$p = (s'$, for some string $s'$, $s' \leq s$] \mbox{} \\ %
      In this case, since $P(s)$ holds, it follows that $s'$ has at
      least as many left as right parentheses.  Thus, the same
      property holds for the string $(s'$.

    \item[$p = (s)$] \mbox{} \\ %
      In this case, since $P(s)$ holds, the string $(s)$ has at least
      as many left as right parentheses.

    \item[$p = (s)t'$, for some string $t'$, $t' \leq t$] \mbox{} \\ %
      In this case, by the previous case, we know that the string
      $(s)$ has at least as many left as right parentheses.  Moreover,
      since $P(t)$ holds, it follows that $t'$ has at least as many
      left as right parentheses.  Thus, it follows that the string
      $(s)t'$ has at least as many left as right parentheses.
    \end{description}

    Thus, any prefix of $(s)t$ has at least as many left as right
    parentheses; that is, $P((s)t)$ holds.  Finally, by universal
    generalization, the inductive step holds for any such $s, t \in
    W$.

  \end{description}

\end{solution}
}

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

%\end{problems}

\collaboration

\end{document}

\endinput 
 

    Let an $2^n \times 2^n \times 2^n$ cube with an arbitrary one-foot
    cubic block missing be denotes as an $n$-cube.

    \begin{theorem*} 
      For any positive integer $n$, any $n$-cube can be build out of
      $1$-cubes.


$2^n \times 2^n \times 2^n$
      cube (an {\em $n$-cube}) with an arbitrary one-foot cubic block
      missing can be built with basic blocks of size $2\times 2\times
      2$ ({\em $1$-cube}) with one of its one-foot cubic blocks
      missing.
    \end{theorem*}
    \begin{proof} 
      Let $P(n)$ be the predicate that an {\em $n$-cube} with one
      arbitrary cubic foot missing can be built using {\em $1$-cubes}
      with .  We use mathematical induction to
      prove $P(n)$ is true for all positive integers $n$.

      {\bf Basis Step} $P(1)$ is true since a {\em $1$-cube} with one
      missing cubic foot is already provided as basic block by CIA.

      {\bf Inductive Step:} Assume that $P(n)$ is true. We show that
      $P(n+1)$ is true. Construct $8$ {\em $n$-cubes} in such a way
      that $7$ of them are missing one cubic foot from one of their
      $8$ corners, and the {\em $8$th} one is missing an arbitrary
      cubic foot. We can do this by the induction hypothesis. We
      construct an {\em $(n+1)$-cube} as follows: Put the $7$
      corner-missing {\em $n$-cubes} together so that all of their
      missing corners meet in the center. Then fill up the gap with a
      basic block.  Now add the {\em $8$th} {\em $n$-cube} with an
      arbitrary cubic foot missing to get an {\em $(n+1)$-cube} with
      an arbitrary cubic foot removed.
    \end{proof}

    Now we are in good shape to prove the master theorem.

    \begin{theorem*}
      Prove that an {\em $(n+1)$-cube} with one cubic foot missing
      from its center (the {\bf CIA} cube) can be built using {\em
        $1$-cubes} with one cubic foot missing.
    \end{theorem*}
    \begin{proof}
      The {\bf CIA} cube can be built by following the steps in the
      proof of {\bf Theorem $0.1$} except that when building the {\em
        $8$th} cube, we choose the arbitrary missing cubic foot to be
      one of the $8$ possible {\em $1$-cubes} in the center of the
      {\em $8$th} {\em $n$-cube}.
    \end{proof}
  \end{solution}

\def\emptystring{}
\def\solutionargument{}

\ifx\solutionargument\emptystring
  {\Huge then}
\else
  {\Huge else}
\fi

\def\solutionargument{ }

\ifx\solutionargument\emptystring
  {\Huge then}
\else
  {\Huge else}
\fi

\def\solutionargument{x}

\ifx\solutionargument\emptystring
  {\Huge then}
\else
  {\Huge else}
\fi


\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}
