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

\showsolutions

\newcommand{\edge}[2]{#1\text{---}#2}
\newcommand{\mfigure}[3]{\bigskip\centerline{\resizebox{#1}{#2}{\includegraphics{#3}}}\bigskip}

\begin{document}

\recitation{10}{October 15, 2004}

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

\newcommand{\bigbox}{\fbox{\vspace{0.5in} \hspace{0.75in}}}

\begin{problem}
Which of these symbols
%
\[
\Theta \qquad O \qquad \Omega \qquad o \qquad \omega
\]
%
can go in these boxes?

{\large
\begin{align*}
2 n + \log n \qquad & = \qquad \bigbox \ ( n ) \\
\insolutions{& \Theta, O, \Omega} \\
\log n \qquad & = \qquad \bigbox \ ( n ) \\
\insolutions{& O, o} \\
\sqrt{n} \qquad & = \qquad \bigbox \ ( \log^{300} n ) \\
\insolutions{& \Omega, \omega } \\
n 2^n \qquad & = \qquad \bigbox \ ( n ) \\
\insolutions{& \Omega, \omega } \\
n^7 \qquad & = \qquad \bigbox \ ( 1.01^n ) \\
\insolutions{& O, o}
\end{align*}
}

\end{problem}

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

\newpage

\begin{problem}
An explorer is trying to reach the Holy Grail, which she believes is
located in a desert shrine $d$ days walk from the nearest
oasis.\footnote{She's right about the location, but doesn't realize
that the Holy Grail is actually just the Bene\u{s} network.}  In the
desert heat, the explorer must drink continuously.  She can carry at
most 1 gallon of water, which is enough for 1 day.  However, she is
free to create water caches out in the desert.

For example, if the shrine were $2/3$ of a day's walk into the desert,
then she could recover the Holy Grail with the following strategy.
She leaves the oasis with 1 gallon of water, travels $1/3$ day into
the desert, caches $1/3$ gallon, and then walks back to the oasis---
arriving just as her water supply runs out.  Then she picks up another
gallon of water at the oasis, walks $1/3$ day into the desert, tops
off her water supply by taking the $1/3$ gallon in her cache, walks
the remaining $1/3$ day to the shine, grabs the Holy Grail, and then
walks for $2/3$ of a day back to the oasis--- again arriving with no
water to spare.

But what if the shrine were located farther away?

\bparts

\ppart What is the most distant point that the explorer can reach and
return from if she takes only 1 gallon from the oasis.?

\solution[\vspace{0.75in}]{At best she can walk $1/2$ day into the
desert and then walk back.}

\ppart What is the most distant point the explorer can reach and
return form if she takes only 2 gallons from the oasis?  No proof is
required; just do the best you can.

\solution[\vspace{1in}]{The explorer walks $1/4$ day into the
desert, drops $1/2$ gallon, then walks home.  Next, she walks $1/4$
day into the desert, picks up $1/4$ gallon from her cache, walks an
additional $1/2$ day out and back, then picks up another $1/4$ gallon
from her cache and walks home.  Thus, her maximum distance from the
oasis is $3/4$ of a day's walk.}

\ppart What about 3 gallons?  (Hint: First, try to establish a cache
of 2 gallons \textit{plus} enough water for the walk home as far into
the desert as possible.  Then use this cache as a springboard for your
solution to the previous part.)

\solution[\newpage]{Suppose the explorer makes three trips $1/6$ day
into the desert, dropping $2/3$ gallon off units each time.  On the
third trip, the cache has 2 gallons of water, and the explorer still
has $1/6$ gllon for the trip back home.  So, instead of returning
immediately, she uses the solution described above to advance another
$3/4$ day into the desert and then returns home.  Thus, she reaches
%
\[
\frac{1}{6} + \frac{1}{4} + \frac{1}{2} = \frac{11}{12}
\]
%
days' walk into the desert.}

\ppart How can the explorer go as far as possible is she withdraws $n$
gallons of water?  Express your answer in terms of the Harmonic number
$H_n$, defined by:
%
\[
H_n = \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \ldots \frac{1}{n}
\]

\solution[\vspace{3in}]{With $n$ gallons of water, the explorer can
reach a point $H_n / 2$ days into the desert.

Suppose she makes $n$ trips $1/(2n)$ days into the desert, dropping of
$(n-1)/n$ gallons each time.  Before she leaves the cache for the last
time, she has $n$ gallons plus enough for the walk home.  So she
applies her $(n-1)$-day strategy to go an additional $H_{n-1} / 2$
days into the desert and then returns home.  Her maximum distance from
the oasis is then:
%
\[
\frac{1}{2n} + \frac{H_{n-1}}{2} = \frac{H_n}{2}
\]
}

\ppart Use the fact that
%
\[
H_n \sim \ln n
\]
%
to approximate your previous answer in terms of logarithms.

\solution[\vspace{1in}]{An approximate answer is $\ln n / 2$.  }

\ppart Suppose that the shrine is $d = 10$ days walk into the desert.
Relying on your approximate answer, how many days must the explorer
travel to recover the Holy Grail?

\solution{
She can obtains the Grail when:
%
\[
\frac{H_n}{2} \approx \frac{\ln n}{2} \geq 10
\]
%
This requires about $n \geq e^{20} = 4.8 \cdot 10^8$ days.
}

\eparts

\end{problem}

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

\end{document}
