\documentclass[12pt,twoside]{article}
\input{macros-course}

\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{graphics}
\usepackage{amsfonts}
\usepackage{amssymb}

\addtolength{\textheight}{.05in}

\begin{document}

\pset{8}{April 17, 2003}{Start of class on Tuesday, April 29}

%\newcommand{\solution}[1]{}                          % hide solutions
\newcommand{\solution}[1]{\textbf{Solution.} #1}    % show solution

\newcommand{\beqn}{\begin{eqnarray*}}
\newcommand{\eeqn}{\end{eqnarray*}}
\newcommand{\ex}[1]{\text{Ex} \left[ #1 \right] }
\newcommand{\pr}[1]{\text{Pr} \left\{ #1 \right\} }

\begin{problems}

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

\problem The 6.042 course staff considered a box-stacking competition
against a team of students.  Naturally, this prompted us to search for
the best way to cheat.  We had two promising ideas:

\begin{problemparts}

\problempart Our first idea was to secretly weight all of our boxes,
moving the center of mass nearer to one end as shown below:

\bigskip
\centerline{\resizebox{!}{1.5in}{\includegraphics{pset8-box.eps}}}
\bigskip

The students would be given ordinary, unweighted boxes.  If both teams
built optimal structures, how much farther would the staff's box stack
extend?  Assume that each team has $n$ boxes.

\solution{As in class, suppose that the edge of the table is position
0.  The rightmost edge of the $k$-th box from the top is at position
$x_k$.  The center-of-mass of the top $k$ boxes is at position $z_k$.
Then we reason as follows:

\beqn
x_{k+1}
	& = &	z_k \\
	& = &	\frac{z_{k-1} \cdot (k-1) +
		(x_k - (1 - 1/r)) \cdot 1}{(k-1) + 1} \\
	& = &	\frac{x_k \cdot k - (1 - 1/r)}{k} \\
	& = &	x_k - \frac{r - 1}{r} \cdot \frac{1}{k}
\eeqn

This implies that the course staff's stack would extend to $(r - 1)/r
\cdot H_n$, which is nearly twice as far as the student stack when
$r$ is large.}

\problempart An alternative idea was to use thinner boxes.  Students
would be given boxes of height 1, but the staff would use boxes of
height $1 / q$ for some $q > 1$.  To create the appearance of
fairness, each team would be given a stack of boxes with total height
$n$.  Of course, this would give the students $n$ ordinary boxes and
would give the staff $qn$ thin boxes.  If both teams now built optimal
structures, how much farther would the staff's stack extend?  Also,
find an approximate answer by using the formula $H_k \approx \ln k$.

\solution{Using the analysis from class, the extension of the student
stack would be $H_{n} / 2$ and the extension of the staff stack wouuld
be $H_{qn} / 2$.  Thus, the staff's winning margin would be:

\beqn
\frac{H_{qn} - H{n}}{2}
	& \approx &	\frac{\ln qn - \ln n}{2} \\
	& = &	\frac{\ln q}{2}
\eeqn

\noindent Thus, for example, if the staff boxes were $1/2$-height, our
winning margin would be $(\ln 2) / 2 = 0.345\ldots$ boxes.
}

\end{problemparts}

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

\problem A bug begins walking across a rug.  The rug is one meter
long, and the bug walks one centimeter per second.  However, at the
end of each second, the rug is given a tug, which instantaneously
stretches it by one meter.  The rug stretches uniformly; that is, the
portion of the rug behind the bug is stretched by the same factor as
the portion ahead of the bug.

To clarify the procedure, here is what happens at the beginning.  In
the first second, the bug walks 1 centimeter.  Then the rug is
instantaneously stretched by one meter, leaving 2 cm behind the bug
and 198 cm ahead.  In the next second, the bug walks another
centimeter, leaving 3 cm of rug behind the bug and 197 cm ahead.  Then
the rug is stretched by another meter, leaving $3 \cdot (3/2) = 4.5$
cm of rug behind the bug and $197 \cdot (3/2) = 295.5$ cm ahead.

Can the bug cross the rug?  If so, approximately how long does it
take?

\solution{In the $k$-th second, the rug is $100k$ centimeters long and
the bug traverses 1 centimeter.  Therefore, the {\em fraction} of the
rug crossed by the bug is $1 / 100k$.  Therefore, the fraction of the
rug crossed by the bug in the first $n$ seconds is:

\beqn
\sum_{k=1}^{n} \frac{1}{100k}
    & = & \frac{1}{100} \cdot H_n \\
    & \approx & \frac{\ln n}{100}
\eeqn

\noindent The bug completes it journey when the fraction of the rug
crossed is 1; that is, when:

\beqn
\frac{\ln n}{100} & \geq & 1 \\
\ln n & \geq & 100 \\
n & \geq & e^{100} \\
 & \approx & 10^{43}
\eeqn

\noindent So the bug does cross the rug, but it takes about $10^{43}$
seconds!
}

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

\problem Use integration to find lower and upper bounds on the
following infinite sum:

\beqn
s & = &
\frac{1}{1^4} + \frac{1}{2^4} + \frac{1}{3^4} + \frac{1}{4^4} + \frac{1}{5^4} + \ldots
\eeqn

To get a really accurate answer, add up the first few terms of the sum
explicitly and then bound the remaining terms using integration.  

\solution{
The sum of the first four terms is:

\beqn
\frac{1}{1^4} + \frac{1}{2^4} + \frac{1}{3^4} + \frac{1}{4^4}
    & = & \frac{22369}{20736}
\eeqn

We can bound the remaining terms using integrals as follows:

\[
\int_4^\infty \frac{1}{(x+1)^4}
    \ \leq \ 
\sum_{i=5}^{\infty}
    \ \leq \ 
\frac{1}{5^4} + \int_5^\infty \frac{1}{x^4}
\]

On the left, we have:

\beqn
\int_4^\infty \frac{1}{(x+1)^4}
    & = & \left. - \frac{1}{3 (1+x)^3} \right|_4^\infty \\
    & = & \frac{1}{375}
\eeqn

On the right, we have:

\beqn
\frac{1}{5^4} + \int_5^\infty \frac{1}{x^4}
    & = & \frac{1}{5^4}+\left.\left(-\frac{1}{3 x^3}\right)\right|_5^\infty \\
    & = & \frac{1}{5^4}+\frac{1}{375}
\eeqn

Putting this all together, we have the bounds:

\[
\frac{22369}{20736} + \frac{1}{375}
\ \leq \ s \ \leq \ 
\frac{22369}{20736} + \frac{1}{5^4} + \frac{1}{375}
\]

In numerical terms, this means:

\[
1.08142\ldots
\ \leq \ s \ \leq \ 
1.08301\ldots
\]

The exact sum is $s = \pi^4 / 90 = 1.0823232337111381915\ldots$.
}

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

\problempart A very tired bug begins at position $(0, 0)$ in the
coordinate plane $\mathbb{N} \times \mathbb{N}$.  Each second, it
either staggers east (incrementing its first coordinate) or wobbles
north (incrementing the second coordinate).

\begin{problemparts}

\problempart By how many different paths can the bug reach point $(x, y)$?

\solution{The number of distinct path is equal to the number of ways
to choose $x$ eastward steps from among a total of $x + y$ steps:

\beqn
\binom{x + y}{x} & = & \binom{x + y}{y}
\eeqn
}

\problempart At the point $(x', y')$, where $0 \leq x' \leq x$ and $0
\leq y' \leq y$, there is a Flaming Chasm of Hideous Death.  If the
bug picks a path to $(x, y)$ uniformly at random, what is the
probability that it falls into the Chasm?

\solution{Every path from $(0, 0)$ to $(x, y)$ via $(x', y')$,
consists of a path from $(0, 0)$ to $(x', y')$ together with a path
from $(x', y')$ to $(x, y)$.  Using the previous result and the
product rule, we find:

\beqn
\pr{\text{visits $(x', y')$}}
	& = &	\frac{\binom{x' + y'}{x'}\binom{(x - x') + (y - y')}{x - x'}}
		{\binom{x + y}{x}}
\eeqn
}

\end{problemparts}

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

\problem In the game of seven-card stud, a player is dealt a hand of
seven cards.  Assume that the deck is thoroughly shuffled, so that
every hand is equally likely.  Solve the problems below and show your
work.  You may leave binomial coefficients in your answers.

Note that each card has a {\em suit} ($\heartsuit$, $\spadesuit$,
$\diamondsuit$, or $\clubsuit$) and a {\em value} (A, 2, 3, 4, \ldots,
9, 10, J, Q, or K).  For this problem, the value of an ace is just
below the value of a 2.  The terms {\em pair}, {\em three-of-a-kind},
and {\em four-of-a-kind} refer to sets of two, three, and four cards
with the same value.

\begin{problemparts}

\problempart How many different hands are possible?

\solution{There is one hand for each way of choosing 7 cards from a
52-card deck.  Therefore, the number of possible hands is:

\[
\binom{52}{7}
\]
}

\problempart What is the probability that all cards in a hand have the
same suit?

\solution{The suit can be chosen in 4 ways.  The values of the seven
cards can be chosen in $\binom{13}{7}$ ways.  Therefore, the
probability is:

\beqn
\pr{\text{all same suit}}
	& = &	\frac{4 \cdot \binom{13}{7}}{\binom{52}{7}}
\eeqn
}

\problempart What is the probability that a hand contains seven cards
with the same suit and consecutive values?

\solution{There are 7 ways to chose the value of the lowest card, and
there are 4 ways to chose the suit.  Therefore, the probability is:

\beqn
\pr{\text{7-card straight flush}} & = &
	\frac{7 \cdot 4}{\binom{52}{7}}
\eeqn
}

\problempart What is the probability that a hand contains a
four-of-a-kind?

\solution{The value of the four-of-a-kind can be chosen in 13 ways.
The rest of the hand may consist of any three cards chosen from the
remaining 48, giving $\binom{48}{3}$ possibilities.  Overall, the
probability is:

\beqn
\pr{\text{4-of-a-kind}} & = &
	\frac{13 \cdot \binom{48}{3}}{\binom{52}{7}}
\eeqn
}

\problempart What is the probability that a hand contains exactly one
pair and no three- or four-of-a-kind?

\solution{First, we can choose the value of the pair in 13 ways.  Then
we must select two of the fours cards with that value; this can be
done in $\binom{4}{2}$ ways.  The other five cards must have distinct
values drawn from the remaining 12 possible values.  This can be done
in $\binom{12}{5}$ ways.  For each of these five cards, we can chose
the suit in 4 ways, giving another $4^5$ possibilities.  In all, we
have:

\beqn
\pr{\text{one pair}}
	& = &	\frac{13 \cdot \binom{4}{2} \cdot \binom{12}{5} \cdot 4^5}
			{\binom{52}{7}}
\eeqn
}

\problempart What is the probability that a hand contains two
three-of-a-kinds, but no four-of-a-kind?

\solution{The values of the three of a kinds can be chosen in
$\binom{13}{2}$ ways.  The suits represented in each three of a kind
can be chosen in $\binom{4}{3}$ ways.  The remaining card can be
chosen from among the $52 - 8 = 44$ with a different value.  In total,
we have:

\beqn
\pr{\text{two three-of-a-kind}}
	& = &	\frac{\binom{13}{2} \cdot \binom{4}{3}^2 \cdot 44}
			{\binom{52}{7}}
\eeqn
}

\problempart What is the probability that there is no pair, no
three-of-a-kind, and no four-of-a-kind?

\solution{This is equivalent to asking for the probability that all
cards have different values.  In that case, the values can be chosen
in $\binom{13}{7}$ ways, and the suit of each card can be chosen in
four ways.  Therefore, the probability is:

\beqn
\pr{\text{no multiples}}
	& = &	\frac{\binom{13}{7} \cdot 4^7}{\binom{52}{7}}
\eeqn
}

\end{problemparts}

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

\problem There are 100 soldiers.  Each morning, they line up for
review in 10 rows with 10 soldiers in each row.  This continues for 60
days.  Prove that there must exist two soldiers who lined up beside
each other in the same row on at least two different occasions.

\solution{We use the pigeonhole principle.  The holes are all the
pairs of soldiers $\{x, y\}$.  A pigeon is a pair $(d, \{x,y\})$ where
$x$ and $y$ are soldiers that stand next to each other on day number
$d$.  The pigeon $(d, \{x, y\})$ is mapped to the hole $\{x, y\}$.

The number of holes is $\binom{100}{2} = 4950$.  The number of pigeons
is $60 \cdot 10 \cdot 9 = 5400$.  Since there are more pigeons than
holes, two pigeons must be mapped to the same hole.  That is, there
must be two soldiers that lined up next to each other on at least two
different occasions.}

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

\problem Prove that the following equation holds for all $r, n \in
\mathbb{N}$:

\beqn
\binom{r}{0} + \binom{r+1}{1} + \binom{r + 2}{2} + \cdots + \binom{r+n}{n}
    & = & \binom{r + n + 1}{n}
\eeqn

\solution{The proof is by induction on $n$.  The induction hypothesis
is the equation above.  For the base case, $n = 0$, this equation
becomes:

\beqn
\binom{r}{0} & = & \binom{r + 1}{0}
\eeqn

This always holds, because both binomials are equal to 1.  Now suppose
that the equation holds for some $n \in \mathbb{N}$.  We show that it
holds for $n+1$ also as follows:

\beqn
\binom{r}{0} + \binom{r+1}{1} + \cdots + \binom{r+n}{n}
    + \binom{r + n + 1}{n + 1}
    & = & \binom{r + n + 1}{n} + \binom{r + n + 1}{n + 1} \\
    & = & \binom{r + (n + 1) + 1}{n + 1}
\eeqn

The first step uses the induction hypothesis, and the second uses the
standard identity:

\beqn
\binom{x}{y} & = & \binom{x - 1}{y} + \binom{x - 1}{y - 1}
\eeqn

The claim follows by induction.
}

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

\end{problems}
\end{document}
