\documentclass[11pt, twoside]{article}

\usepackage{psfig}

\input{macros-course}

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

\printlayout

\begin{document}

\pset{2}{February 8, 2000}{2:35pm in lecture, February~15,~2000}

\hrule
\vspace*{0.5\baselineskip}

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

\vfill

\mbox{}

\newpage

\textbf{Required Problems:}

\vspace*{0.5\baselineskip}

\begin{fminipage}
{\bf Remember} to include a \emph{collaboration statement} on the
front page of your solutions.  \\
(See Handout 1, \emph{Course Information}.)
\end{fminipage}

\begin{problems}

%Regular 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.


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


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

\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=ps2.eps,height=2.0in}}
\caption{Some of the shapes that Math Moose created.} \label{fig:squares}
\end{figure}

\newpage

\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=cube.ps,height=1in}}
\end{figure}

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


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

(a) 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?

(b) Prove that $k$ is the smallest such number.

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


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

\problem
% tournaments?

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

(a) 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.

(b) 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.

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

\end{problems}

\begin{fminipage}
{\bf Remember} to include a \emph{collaboration statement} on the
front page of your solutions.  \\
(See Handout 1, \emph{Course Information}.)
\end{fminipage}

\end{document}

\endinput 

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

Let $F_n$ be the $n^{\text{th}}$ Fibonacci number, for all $n \in
\mathbb{N}$.  Recall that the Fibonacci numbers are defined
recursively as follows: $F_0 = 0$, $F_1 = 1$, and $F_n = F_{n-1} +
F_{n-2}$, for all $n \in \mathbb{N}, n \geq 2$.

(a) Prove that for all $n \in \mathbb{N}$, $\sum_{i = 0}^{n} F_i =
F_{n + 2} - 1$.

(b) Find a formula for $\sum_{i = 0}^{n} F_{2 i}$ and prove that the
formula is correct.

\problem
% structural induction

The recursive definition of the set $F$ of full binary trees is like the
one for binary trees, except that we only allow the recursive
definition step that includes both a left and a right child.

(a) Give the structural inductive definition.

(b) Define the function numleaves $F$, giving the number of
``leaves''; that is, the number of nodes that have no children.  Your
definition should be recursive, based on the recursive definition of
$F$.

(c) Define the function numinternal on $F$, giving the number of
``internal'' nodes; that is, the number of nodes that do have
children.

(d) Prove by structural induction that for any full binary tree $t$ in
$F$, numleaves(t) = 1 + numinternal(t).

