%  For second problem set
%    WOP - eqn
%    disease spread
%    final exam question on Fn rel primality
%  
%  For third recitation:
%    temple of forever
%    Nicole's problem

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

%  Induction problems:
%
%  FALL 04 PSET
%  1 3 5 / 2 4 6
%  DeMoivre
%  sum of cubes = square of sum
%  general AMGM
%  (1 + 1/ i)
%  unstacking with a + b
%
%  FALL 04 REC 1
%  sum i (i+1)
%  geometric sum ***
%  false proof:  missing base case
%
%  FALL04 REC 2  (GOOD FOR REC 2)
%
%  pirate raid


%  OPTIONS
%  * harmonic number problem (spring 04 pset)
%  * partition into 4's and 5's (spring 04 pset, make 3's and 4's)
%  * maximum product for fixed sum (spring 04 pset)
%  splitting candy bar (spring 04 F3 rec)  (GOOD FOR REC 2)
%

%  Try to base something on Nicole's problem?


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

\documentclass[twoside,12pt]{article}
\usepackage{light}

% \hidesolutions
\showsolutions

\begin{document}

\problemset{2}{February 8, 2005}{Monday, February 14 at 9 PM in Room 32-044}

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

\begin{problem}
Use induction to prove that
%
\[
\left(1 - \frac{1}{2}\right)
\left(1 - \frac{1}{3}\right)
\left(1 - \frac{1}{4}\right)
\cdots
\left(1 - \frac{1}{n}\right)
= \frac{1}{n}
\]
%
for all $n \geq 2$.
\end{problem}

\solution{The proof is by induction on $n$.  Let $P(n)$ be the
proposition that the equation above holds.

\noindent \textit{Base case.}  $P(2)$ is true because
%
\[
\left(1 - \frac{1}{2}\right) = \frac{1}{2}
\]

\noindent \textit{Inductive step.}  Assume $P(n)$ is true.  Then we
can prove $P(n+1)$ is also true as follows:
%
\begin{align*}
\left(1 - \frac{1}{2}\right)
\left(1 - \frac{1}{3}\right)
\cdots
\left(1 - \frac{1}{n}\right)
\left(1 - \frac{1}{n+1}\right)
& = \frac{1}{n} \cdot \left(1 - \frac{1}{n+1}\right) \\
& = \frac{1}{n+1}
\end{align*}
%
The first step uses the assumption $P(n)$ and the second is
simplification.

Thus, $P(2)$ is true and $P(n)$ implies $P(n+1)$ for all $n \geq 2$.
Therefore, $P(n)$ is true for all $n \geq 2$ by the principle of
induction.}

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

\begin{problem}
DeMorgan's Law for sets says:
%
\[
A \cap (B \cup C) = (A \cap B) \cup (A \cap C)
\]
%
Assume this and prove this extension of DeMorgan's Law to $n \geq 2$
sets:
%
\[
A \cap (B_1 \cup B_2 \cup \ldots \cup B_n)
    = (A \cap B_1) \cup (A \cap B_2) \cup \ldots \cup (A \cap B_n)
\]
%
Extending formulas to an arbitrary number of terms is a common (if
mundane) application of induction.
\end{problem}

\solution{We use induction.  Let $P(n)$ be the proposition that
%
\[
A \cap (B_1 \cup B_2 \cup \ldots \cup B_n)
    = (A \cap B_1) \cup (A \cap B_2) \cup \ldots \cup (A \cap B_n)
\]
%
for all sets $A$ and $B_1, \ldots, B_n$.

\noindent \textit{Base case:} $P(2)$ follows from DeMorgan's original
law with $B = B_1$ and $C = B_2$.

\noindent \textit{Inductive step:} Assuming $P(n)$, we can deduce
 $P(n+1)$ as follows:
%
\begin{align*}
A \cap (B_1 \cup B_2 \cup B_3 \cup \ldots \cup B_n)
    & = A \cap ((B_1 \cup B_2) \cup B_3 \cup \ldots \cup B_n) \\
    & = (A \cap (B_1 \cup B_2)) \cup (A \cap B_3) \cup \ldots \cup (A \cap B_n) \\
    & = (A \cap B_1) \cup (A \cap B_2)) \cup (A \cap B_3) \cup \ldots \cup (A \cap B_n)
\end{align*}
%
In the first step, we group $B_1$ and $B_2$.  This allows us to apply
the assumption $P(n)$ in the second step.  The last step uses
DeMorgan's original law.

Since $P(2)$ is true and $P(n) \implies P(n+1)$ for all $n \geq 2$,
the principle of induction implies that $P(n)$ is true for all $n \geq
2$.}

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


\begin{problem}
Let $H_n$ denote the {\em $n$-th harmonic sum}, which is defined by:

\begin{eqnarray*}
H_n & = & \sum_{k = 1}^n \frac{1}{k}
\end{eqnarray*}

Harmonic sums come up often.  You'll see them again later in 6.042 and
also in 6.046.

\begin{claim*}
$H_{2^m} \geq 1 + m / 2$ for all $m \geq 0$.
\end{claim*}

\bparts

\ppart The {\em next} problem part will ask you to prove this claim by
induction.  To make this easier, three steps that you may find useful
in your proof are listed below.  Provide a one sentence justification
for each of these steps.

\begin{eqnarray*}
H_{2^{m+1}}
    & = & \sum_{k = 1}^{2^{m+1}} \frac{1}{k} \\
    & = & H_{2^m} + \sum_{k = 2^m + 1}^{2^{m+1}} \frac{1}{k} \\
    & \geq & H_{2^m} + 2^m \cdot \frac{1}{2^{m+1}} \\
\end{eqnarray*}

\solution{The first step uses the definition of $H_{2^{m+1}}$.  The
second step uses the fact that the first $2^m$ terms of the sum are
equal to all $2^m$ terms of $H_{2^m}$.  The third step uses the fact
that a sum is lower bounded by the number of terms times the smallest
term.}

\ppart Prove the claim by induction.  (See?  We {\em told} you this
was going to happen\ldots)

\solution{We prove the claim by induction.  Let $P(m)$ be the
proposition that $H_{2^m} \geq 1 + m / 2$.

\noindent \textit{Base case.}  Note that $P(0)$ is true, because:
%
\[
H_{2^0} = H_1 = 1 \geq 1 + 0 / 2
\]

\noindent \textit{Inductive step.}  We must show that $P(m)$ implies
$P(m + 1)$ for all $m \geq 0$.  We assume that $P(m)$ is true and
reason as follows:
%
\begin{eqnarray*}
H_{2^{m+1}}
    & = & \sum_{k = 1}^{2^{m+1}} \frac{1}{k} \\
    & = & H_{2^m} + \sum_{k = 2^m + 1}^{2^{m+1}} \frac{1}{k} \\
    & \geq & H_{2^m} + 2^m \cdot \frac{1}{2^{m+1}} \\
    & \geq & (1 + m / 2) + 1 / 2\\
    & = & 1 + (m + 1) / 2
\end{eqnarray*}
%
The first step uses the definition of $H_{2^{m+1}}$.  The second step
uses the fact that the first $2^m$ terms of the sum are equal to all
$2^m$ terms of $H_{2^m}$.  The third step uses the fact that a sum is
lower bounded by the number of terms times the smallest term.  The
fourth step uses our assumption $P(m)$ and simplification.  The last
step uses only algebra.  This shows that $P(m + 1)$ is true, and so
$P(m)$ is true for all $m \geq 0$ by induction.}

\ppart Show that this implies $H_n \geq 1 + \frac{1}{2} \log_2 n$ when
$n$ is a power of 2.

\solution{This inequality follows from substituting $n = \log_2 m$
into the claim.}

\eparts

\end{problem}

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


\begin{problem}
Suppose we want to divide a class of $n$ students into groups each
containing either 4 or 5 students.

\bparts

\ppart Let's try to use strong induction to prove that a class with $n
\geq 8$ students can be divided into groups of 4 or 5.

\begin{proof}
The proof is by strong induction.  Let $P(n)$ be the proposition that
a class with $n$ students can be divided into teams of 4 or 5.

\noindent \textit{Base case.}  We prove that $P(n)$ is true for $n =
8$, 9, or 10 by showing how to break classes of these sizes into
groups of 4 or 5 students:

\begin{eqnarray*}
8 & = & 4 + 4 \\
9 & = & 4 + 5 \\
10 & = & 5 + 5
\end{eqnarray*}

\noindent \textit{Inductive step.}  We must show that $P(8), \ldots,
P(n)$ imply $P(n + 1)$ for all $n \geq 10$.  Thus, we assume that
$P(8), \ldots, P(n)$ are all true and show how to divide up a class of
$n + 1$ students into groups of 4 or 5.  We first form one group of 4
students.  Then we can divide the remaining $n - 3$ students into
groups of 4 or 5 by the assumption $P(n - 3)$.  This proves $P(n +
1)$, and so the claim holds by induction.
\end{proof}

This proof contains a critical logical error.  Identify the first
sentence in the proof that does not follow and explain what went
wrong.  (Pointing out that the \textit{claim} is false is not
sufficient; you must find the first logical error in the
\textit{proof}.)

\solution{The first error is in the sentence:

\begin{quotation}
\noindent Then we can divide the remaining $n - 3$ students into
groups of 4 or 5 by the assumption $P(n - 3)$.
\end{quotation}

If $n = 10$, then $P(n - 3) = P(7)$, which is not among our
assumptions $P(8), \ldots, P(n)$.  In this case, $P(n + 1) = P(11)$ is
actually false.}

\ppart Provide a correct strong induction proof that a class with $n
\geq 12$ students can be divided into groups of 4 or 5.

\solution{The proof is by strong induction.  Let $P(n)$ be the
proposition that a class with $n$ students can be divided into teams
of 4 or 5.

\noindent \textit{Base case.}  We prove that $P(n)$ is true for $n =
12$, 13, 14, and 15 by showing how to break classes of these sizes
into groups of 4 or 5 students:

\begin{eqnarray*}
12 & = & 4 + 4 + 4 \\
13 & = & 4 + 4 + 5 \\
14 & = & 4 + 5 + 5 \\
15 & = & 5 + 5 + 5
\end{eqnarray*}

\noindent \textit{Inductive step.}  We must show that $P(12), \ldots,
P(n)$ imply $P(n + 1)$ for all $n \geq 15$.  Thus, we assume that
$P(12), \ldots, P(n)$ are all true and show how to divide up a class
of $n + 1$ students.  We first form one group of 4 students.  Then we
can divide the remaining $n - 3$ students into groups of 4 or 5 by the
assumption $P(n - 3)$.  (Note that $n \geq 15$ and so $n - 3 \geq 12$;
thus, $P(n - 3)$ is among our assumptions $P(12), \ldots, P(n)$.)
This proves $P(n + 1)$, and so the claim holds by induction.}

\eparts

\end{problem}

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

\begin{problem}
\begin{claim*}
If a collection of positive integers (not necessarily distinct) has
sum $n \geq 1$, then the collection has product at most $3^{n/3}$.
\end{claim*}

For example, the collection 2, 2, 3, 4, 4, 7 has the sum:

\begin{eqnarray*}
2 + 2 + 3 + 4 + 4 + 7 & = & 22
\end{eqnarray*}

On the other hand, the product is:

\begin{eqnarray*}
2 \cdot 2 \cdot 3 \cdot 4 \cdot 4 \cdot 7
    & = & 1344 \\
    & \leq & 3^{22/3} \\
    & \approx & 3154.2
\end{eqnarray*}

\bparts

\ppart As a preliminary step, use strong induction to prove that $n
\leq 3^{n/3}$ for every integer $n \geq 0$.

\solution{The proof is by strong induction.  Let $P(n)$ be the
proposition that $n \leq 3^{n/3}$.

\noindent \textit{Base case.}  We show that $P(0)$, $P(1)$, $P(2)$,
$P(3)$, and $P(4)$ are true:
%
\begin{eqnarray*}
0^3 \leq 3^0 & \rightarrow & 0 \leq 3^{0/3} \\
1^3 \leq 3^1 & \rightarrow & 1 \leq 3^{1/3} \\
2^3 \leq 3^2 & \rightarrow & 2 \leq 3^{2/3} \\
3^3 \leq 3^3 & \rightarrow & 3 \leq 3^{3/3} \\
4^3 \leq 3^4 & \rightarrow & 4 \leq 3^{4/3} \\
\end{eqnarray*}
%
Each implication follows by taking cube roots.

\noindent \textit{Inductive step.}  Now, we show that $P(0), \ldots,
P(n)$ imply $P(n + 1)$ for all $n \geq 4$.  Thus, we assume that
$P(0), \ldots, P(n)$ are all true and reason as follows:
%
\begin{eqnarray*}
3^{(n + 1)/3}
    & = & 3 \cdot 3^{(n-2)/3} \\
    & \geq & 3 \cdot (n - 2) \\
    & \geq & n + 1 \hspace{1in} \text{(for all $n \geq 7/2$)}
\end{eqnarray*}
%
The first step is algebra.  The second step uses our assumption $P(n -
2)$.  The third step is a linear inequality that holds for all $n \geq
7/2$.  (This forced us to deal individually with the cases $P(3)$ and
$P(4)$, above.) Therefore, $P(n + 1)$ is true, and so $P(n)$ is true
for all $n \geq 0$ by induction.}

\ppart Prove the claim using induction or strong induction.  (You may
find it easier to use induction on the {\em number of positive
integers in the collection} rather than induction on the sum $n$.)

\solution{We use induction on the size of the collection.  Let $P(k)$
be the proposition that every collection of $k$ positive integers with
sum $n$ has product at most $3^{n/3}$.  First, note that $P(1)$ is
true by the preceding problem part.

Next, we must show that $P(k)$ implies $P(k + 1)$ for all $k \geq 1$.
So assume that $P(k)$ is true, and let $x_1, \ldots, x_{k+1}$ be a
collection of positive integers with sum $n$.  Then we can reason as
follows:

\begin{eqnarray*}
x_1 \cdot x_2 \cdots x_k \cdot x_{k+1}
    & \leq & 3^{(n - x_{k+1}) / 3} \cdot x_{k+1} \\
    & \leq & 3^{(n - x_{k+1}) / 3} \cdot 3^{x_{k+1} / 3} \\
    & = & 3^{n / 3}
\end{eqnarray*}

The first step uses the assumption $P(k)$, the second uses the
preceding problem part, and the last step is algebra.  This shows that
$P(k + 1)$ is true, and so the claim holds by induction.
}

\eparts

\end{problem}

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

\begin{problem}
Suppose that you take a piece of paper and draw $n$ straight lines, no
one exactly on top of another, that completely cross the paper.  This
divides the paper into polygonal regions.  Prove by induction that you
can color each region either red or blue so that two regions that
share a boundary are always colored differently.  (Regions that share
only a boundary point may have the same color.)

\end{problem}

\solution{The proof is by induction.  Let $P(n)$ be the proposition
that the regions defined by $n$ lines can be colored red or blue so
that adjacent regions are different colors.

\noindent \textit{Base case:} If $n = 0$, then there are no lines and
the whole paper is a single region.  Color it red.  Adjacent regions
are different colors trivially since there are no adjacent regions.
Thus, $P(0)$ is true.

\noindent \textit{Inductive step:} Assume that $P(n)$ is true.  We
prove that $P(n+1)$ is also true.  Given a configuration of $n + 1$
lines, remove an arbitrary line $l$.  By the assumption $P(n)$, the
polygonal regions defined by the remaining $n$ lines can be colored
red or blue so that adjacent regions are colored differently.  Now add
back the line $l$ and invert the color of every region to one side of
$l$.  Adjacent regions on the same side of the line are different
colors by the induction assumption $P(n)$.  Adjacent region on
opposite sides of the line are different colors because the colors on
one side were inverted.  Therefore, $P(n)$ implies $P(n+1)$, and so
$P(n)$ is true for all $n \geq 0$ by induction.}

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

\begin{problem}
Let's consider a variation of the Unstacking game demonstrated in
lecture.  As before, the player is presented with a stack of $n \geq
1$ bricks.  Through a sequence of moves, she must reduce this to $n$
single-brick stacks while scoring as many points as possible.  A move
consists of dividing a single stack of $(a + b)$ bricks (where $a, b >
0$) into two stacks with heights $a$ and $b$.  Suppose that this move
is worth $a + b$ points.  Find the best strategy and use induction to
prove that there is no better strategy.
\end{problem}

\solution{Some experimentation suggests that the best strategy is to
remove one block at a time.  This gives a score of:
%
\begin{align*}
n + (n-1) + \ldots + 3 + 2
    & = \frac{n(n+1)}{2} - 1 \\
    & = \frac{(n+2)(n-1)}{2}
\end{align*}
%
Now we must prove that there is no better strategy.

\begin{proof}
We use strong induction.  Let $P(n)$ be the proposition that
unstacking $n$ bricks is worth at most $(n+2)(n-1)/2$ points.

\noindent \textit{Base case:} $P(1)$ is true because the game ends
immediately when there is only 1 brick.  Thus, the player's score is
0, which is the value of $(n+2)(n-1)/2$ when $n = 1$.

\noindent \textit{Inductive step:} Now assume that $P(1), \ldots,
P(n-1)$ are all true in order to prove $P(n)$, where $n \geq 2$.
Suppose the stack of $n$ bricks is split into stacks of height $x$ and
$n - x$, where $0 < x < n$.  The player's best possible score for the
game is then:
%
\[
\underbrace{((n-x) + x)}_{\text{for first move}} +
\underbrace{(x+2)(x-1)/2}_{\text{to unstack $x$ bricks}} +
\underbrace{(n-x+2)(n-x-1)/2}_{\text{to unstack $n - x$ bricks}}
\]
%
Here we are using the assumptions $P(x)$ and $P(n-x)$, which specify
the best possible scores for unstacking $x$ and $n - x$ bricks.  Now
we must choose $x$ to maximize this expression.  The derivative with
respect to $x$ is $2x - n$.  Thus, the expression decreases as $x$
grows from 1 to $n/2$ and then increases symmetrically as $x$ grows

from $n/2$ to $n-1$.  Therefore, the maximum is achieved when $x = 1$
or $x = n - 1$.  In both cases, the expression above is equal to:
%
\[
\frac{(n+2)(n-1)}{2}
\]
%
So we have shown that $P(1)$, \ldots, $P(n-1)$ imply $P(n)$.

Therefore, $P(n)$ is true for all $n \geq 1$ by the strong induction
principle.
\end{proof}
}


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

\end{document}
