Pset 2:

Self-study: I gave this to Carl.

Self-study problems: I gave this to Carl.

Regular reading: I gave this to Carl.

Regular problems:

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

Prove by induction that
$\forall n \geq 1 [n^3 + (n+1)^3 + (n+2)^3 \mbox{ is evenly 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 shapes that Theory Pig created.} \label{fig:squares}
\end{figure}

\problem
% strengthen inductive hypothesis
% source:  fall96

The C.I.A. wants you 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 -- see 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
inductively 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 {\em can\/} be split into teams of 4 and 7?

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

(c) Prove (by induction) that $k$ does work, that is, 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 5

Prove the following identities involving Fibonacci numbers:
(a) part 1
(b) part d


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

A sequence $G_0, G_1, G_2,\ldots$ is defined recursively as follows:
$G_0 = 0$
$G_1 - 1$
for every n geq 2, $G_n = 5G_{n-1} - 6 G_{n-2}$

Prove that for all n \geq 0, G_n = 3^n - 2^n

\problem
% tournaments?

Construct the following rankings for $n$-player tournaments, 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, \not \exists A, B, C [A beats B \wedge B beats C \wedge C
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:

(format)

empty string is in W
if s and t are in W then the string (s)t is in W.

Using structural induction, prove: 
In any well-formed parenthesis string, any prefix has at least as many
left parentheses as right parentheses.

\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 all full binary trees t,
numleaves(t) = 1 + numinternal(t).



