\documentclass[12pt,oneside]{article}

\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{graphics}
\input{macros-course}

\begin{document}

%\exam{\ Final Exam}{December 15, 1998}
%\newcommand{\solution}[1]{}
%\newcommand{\sol}[1]{}
%\newcommand{\examonly}[1]{#1}
%\newcommand{\us}[1]{#1}

\exam{Final Exam Solutions}{December 15, 1998}
\newcommand{\solution}[1]{\bigskip #1}
\newcommand{\sol}[1]{#1}
\newcommand{\examonly}[1]{}
\newcommand{\us}[1]{\underline{#1}}

\newcommand{\unspace}{\vspace{-0.75ex}}
\newcommand{\Ex}{\text{Ex}}

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

\examonly{
\setcounter{page}{0}

\vspace{0.5in}

{\bf YOUR NAME:}  \underline{\hspace{3in}}

\vspace{0.5in}

{\bf YOUR TA:}  \underline{\hspace{3in}}

\vspace{0.5in}

\begin{itemize}
\item This exam is open book, open notes.

\item {\bf Show your work as fully and as clearly as possible};
partial credit will be given.

\item Write your solutions in the spaces provided.

\item Do not discuss this exam with students who have not yet taken
it.
\end{itemize}

\[
\begin{array}{|c|c|c|} \hline
\text{Problem} & \text{Points} & \text{Score} \\
 \hline  1 & 10 & \\
 \hline  2 & 15 & \\
 \hline  3 & 12 & \\
 \hline  4 & 10 & \\
 \hline  5 & 20 & \\
 \hline  6 &  8 & \\
 \hline  7 & 10 & \\
 \hline  8 &  5 & \\
 \hline  9 &  5 & \\
 \hline 10 & 10 & \\
 \hline 11 & 10 & \\
 \hline 12 &  5 & \\
 \hline 13 & 10 & \\
 \hline 14 & 10 & \\
 \hline 15 & 10 & \\ \hline
\text{TOTAL}	& 150	& \\ \hline
\end{array}
\]

\newpage
}

\begin{problems}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%		OLD STUFF
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\examonly{\newpage}

\problem {\bf (10 points)} Suppose that $A$ and $B$ are non-empty sets
such that $A$ is strictly contained in $B$.  Mark each statement below
{\bf T}rue or {\bf F}alse.

\bigskip

\begin{tabular}{ll}
\underline{\hspace{1cm}} & Set $A$ is finite iff set $B$ is
finite. \\
& \sol{(False.)} \\
\underline{\hspace{1cm}} & If $B$ is finite, then there must
exist a surjection mapping $B$ to $A$. \\
& \sol{(True.)} \\
\underline{\hspace{1cm}} & If $B$ is finite, then there must
exist an injection mapping $A$ to $B$. \\
& \sol{(True.)} \\
\underline{\hspace{1cm}} & If $B$ is finite and there is a bijection
mapping $A$ to $B \setminus A$, then $|B| = 2 |A|$. \\
& \sol{(True.)} \\
\underline{\hspace{1cm}} & There can not exist a bijection from $A$ to
$B$. \\
& \sol{(False.)} \\
\end{tabular}

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

\examonly{\newpage}

\problem {\bf (15 points)} Consider the following procedure for
computing the greatest common divisor ($\gcd$) of a non-empty list of
positive integers $(x_1, x_2, \ldots, x_n)$.

If all entries in the list are equal, then the procedure outputs the
common value and terminates.  Otherwise, the procedure selects two
entries with different values and replaces the larger one by the
difference.

We can model this procedure with a state machine as follows.

\begin{itemize}

\item The set of states $Q$ consists of all lists of $n$ positive
integers.

\item The set of start states $Q_0$ consists of the single state $(x_1,
x_2, \ldots, x_n)$.

\item The set $\delta$ contains all transitions of the form

\begin{eqnarray*}
(y_1, y_2, \ldots, y_i, \ldots, y_j, \ldots, y_n)
	& \rightarrow &
(y_1, y_2, \ldots, y_i - y_j, \ldots, y_j, \ldots, y_n)
\end{eqnarray*}

where $i$ and $j$ are distinct numbers in the range $1$ to $n$ and
$y_i > y_j$.  (Note that the transition is written with $y_i$
preceding $y_j$, but that the reverse order is also possible.)

\end{itemize}

\begin{problemparts}

\problempart {\bf (5 points)} Prove that the procedure terminates.

\solution{We construct a non-negative, decreasing derived variable.
This implies that the machine reaches at state with no outgoing
transitions.  All such states are terminating states of the procedure.

Define the derived variable $S$ to take on the value $y_1 + y_2 +
\ldots + y_n$ in the state corresponding to the list $(y_1, y_2,
\ldots, y_n)$.  This derived variable is non-negative, since all $y_i$
are positive.  The derived variable is decreased by each transition,
since the list entry $y_i$ is decrease by $y_j$ (a positive quantity)
and all other list entries are unchanged.}

\examonly{\newpage}

\problempart {\bf (10 points)} Prove that the procedure computes the
$\gcd$ of $x_1, x_2, \ldots, x_n$.  State explicitly any number theoretic
facts that you use, but do not prove them.

\solution{The proof uses the Invariant Theorem.  We will prove the
invariant that in state $(y_1, y_2, \ldots, y_n)$,

\begin{eqnarray*}
\gcd(y_1, y_2, \ldots, y_n) & = & \gcd(x_1, x_2, \ldots, x_n).
\end{eqnarray*}

The invariant hold trivially in the start state.  Futhermore, the
invariant holds after a transition if it holds prior to a transition:

\begin{eqnarray*}
\gcd(y_1, y_2, \ldots, y_i - y_j, \ldots, y_j, \ldots, y_n)
	& = &	\gcd(y_1, y_2, \ldots, y_i, \ldots, y_j, \ldots, y_n) \\
	& = &	\gcd(x_1, x_2, \ldots, x_n)
\end{eqnarray*}

The first step is justified by the following number-theoretic fact.
For positive integers $z_1, z_2, \ldots, z_n$,

\begin{eqnarray*}
\gcd(z_1, z_2, \ldots, z_i, \ldots, z_j, \ldots, z_n)
	& = &	\gcd(z_1, z_2, \ldots, z_i - z_j, \ldots, z_j, \ldots, z_n)
\end{eqnarray*}

provided $z_i > z_j$.  The second step in the argument above is
justified by the assumption that the invariant holds prior to the
transition.  Therefore, the invariant holds by the Invariant Theorem.

This invariant implies that the output of the procedure is correct.
If $(y_1, y_2, \ldots, y_n)$ is a terminating state, then

\begin{eqnarray*}
y_1 = y_2 = \ldots = y_n
	& = &	\gcd(y_1, y_2, \ldots, y_n) \\
	& = &	\gcd(x_1, x_2, \ldots, n_n).
\end{eqnarray*}

The second step uses the invariant.
}
\end{problemparts}

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

\examonly{\newpage}

\problem {\bf (12 points)} Find a closed-form expression for $T(N)$ in
each problem part.  Your answer may make use of $\Theta$ notation.  No
proofs are required.

\begin{problemparts}

\problempart {\bf (6 points)}

\begin{eqnarray*}
T(n)	& = &	\sum_{i=1}^n \frac{i^2 + 6 \sqrt{i}}{i \sqrt{i}}
\end{eqnarray*}

\examonly{\vspace{2.5in}}

\solution
{
\begin{eqnarray*}
T(n)	& = &	\sum_{i=1}^n \frac{i^2 + 6 \sqrt{i}}{i \sqrt{i}} \\
	& = &	\sum_{i=1}^n \frac{i^2}{i \sqrt{i}} +
		\sum_{i=1}^n \frac{6 \sqrt{i}}{i \sqrt{i}} \\
	& = &	\sum_{i=1}^n \sqrt{i} +
		\sum_{i=1}^n \frac{6}{i} \\
	& = &	\Theta\left(n^{3/2} + \ln n\right) \\
	& = &	\Theta\left(n^{3/2}\right)
\end{eqnarray*}
}

\problempart {\bf (6 points)}

\begin{eqnarray*}
T(n)	& = &	\left\{
\begin{array}{cl}
1	&	\text{for} \quad n \leq 5 \\
\frac{1}{2} T(\left\lfloor\frac{n}{2} + \log{n}\right\rfloor) + \frac{2}{n}
	&	\text{for} \quad n > 5
\end{array}
\right.
\end{eqnarray*}

\solution{ We apply Akra-Bazzi.  First, we find the parameter $p$ by
solving the equation

\begin{eqnarray*}
\frac{1}{2} \cdot \left( \frac{1}{2} \right)^p	& = &	1.
\end{eqnarray*}

The solution is $p = -1$.  Therefore, we have

\begin{eqnarray*}
T(n)	& = &	\Theta\left(n^{-1} \cdot \left(
	1 + \int_1^n \frac{\left(\frac{2}{u}\right)}{u^{-1 + 1}} \ du
	\right)\right) \\
	& = &	\Theta\left(n^{-1} \cdot \left(
	1 + 2 \ln n
	\right)\right) \\
	& = &	\Theta\left(\frac{\ln n}{n}\right)
\end{eqnarray*}
}

\end{problemparts}

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

\examonly{\newpage}

\problem {\bf (10 points)} Suppose that five points are placed inside
a square with sides of length 1.  Prove that the distance between some
pair of points is at most $\sqrt{2}/2$.

\solution{Divide the square into four subsquares with edge-length
$\frac{1}{2}$.  By the pigeonhole principle, some two of the five
points must be placed inside the same subsquare.  The distance between
these two points can be at most $\sqrt{2}/2$.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%		COMBINATORICS
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\examonly{\newpage}

\problem {\bf (20 points)} Solve the following counting problems.
Simplified answers are not required.

\begin{problemparts}

\problempart {\bf (4 points)} In how many ways can the letters in
BOOKKEEPER be arranged?

\examonly{\vspace{1in}}

\solution{
\[
\frac{10!}{2! \ 2! \ 3!}
\]
}

\problempart {\bf (4 points)} In how many ways can 160 distinguishable
students be assigned to 8 indistinguishable recitations so that every
recitation has 20 students?

\examonly{\vspace{1in}}

\solution{If the recitations were distinguishable, then the answer
would be $\frac{160!}{20!^8}$ by the multinomial formula.  Since the
recitations are identical, the answer is $\frac{160!}{20!^8 \ 8!}$ by
the quotient rule.
}

\problempart {\bf (4 points)} In how many ways can 6.042 TA John Dunagan assign
the following objects to three desk drawers,

\begin{itemize}
\item 7 tasty treats,
\item 27 thumb tacks, and
\item 1 can of theoretically-enriched Spam,
\end{itemize}

so that the Spam shares a drawer with no tasty treats and at least 19
thumb tacks?  (Desk drawers are distinguishable, but tasty treats and
thumbtacks are not.)

\examonly{\vspace{1in}}

\solution{Theory Pig (R. I. P.) and the tacks can be assigned to a
drawer in 3 ways.  The treats can be divided between the other two
drawers in $\binom{7+1}{1} = 8$ ways.  The 8 remaining tacks can be
divided among the three drawers in $\binom{8+2}{2} = 45$ ways.
Overall, there are $3 \cdot 8 \cdot 45$ assignments.}

\problempart {\bf (4 points)} How many ways can 100 identical balls be
placed in 10 distinguishable bins so that every bin contains an odd
number of balls?

\examonly{\vspace{1in}}

\solution{First, we put 1 ball into each bin.  Then we pair up the 90
remaining balls into 45 pairs.  Then we assign the 45 pairs to bins.
This can be done in $\binom{45 + 9}{9}$ ways.}

\problempart {\bf (4 points)} How many paths are there from $(0, 0)$
to $(4, 4)$ consisting of 10 steps, each of which is either north,
south, east, or west?

\examonly{\vspace{1in}}

\solution{Either there are 5 north steps, 1 south step, and 4 east
steps, or else there are 5 east steps, 1 west step, and 4 north
steps.  Thus, there are

\[
2 \cdot \frac{10!}{5! \ 1! \ 4!}
\]

paths in total.}

\end{problemparts}

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

\examonly{\newpage}

\problem {\bf (8 points)} Some MIT students go for dinner at the
Border Cafe in Harvard Square.  They want to order enough appetizers
to feed everyone.  Chili con queso will feed one person, Tejas chicken
will feed two people, and quesadillas will feed three people.  Write
the generating function for the number of different appetizer orders
that will feed exactly $n$ people.

\examonly{\vspace{3in}}

\solution{
\[
\frac{1}{1-x} \cdot \frac{1}{1-x^2} \cdot \frac{1}{1-x^3}
\]
}

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

\examonly{\newpage}

\problem {\bf (10 points)} The following identity holds for non-negative
integers $n$, $j$, and $k$ such that $n \geq j + k$.

\begin{eqnarray*}
\binom{n}{j} \binom{n-j}{k}
	& = &	\binom{n}{j+k} \binom{j+k}{k}
\end{eqnarray*}

\begin{problemparts}
\problempart {\bf (5 points)} Prove the identity algebraically.

\examonly{\vspace{3in}}

\solution{
\begin{eqnarray*}
\binom{n}{j} \binom{n-j}{k}
	& = &	\frac{n!}{j! \ (n-j)!} \cdot
		\frac{(n-j)!}{k! \ (n-j-k)!} \\
	& = &	\frac{n!}{j! \ k! \ (n-j-k!)} \\
	& = &	\frac{n!}{(j+k)! \ (n-j-k)!} \cdot
		\frac{(j+k)!}{k! \ j!} \\
	& = &	\binom{n}{j+k} \binom{j+k}{k}
\end{eqnarray*}
}

\problempart {\bf (5 points)} Prove the identity combinatorially.

\solution{Both sides of the equation count the number of ways to
choose distinguishable, disjoint subsets of sizes $j$ and $k$ from a
set of $n$ elements.  On the left side, we first choose the
$j$-element subset from the whole $n$-element set, and then choose the
$k$-element subset from the remaining $n-j$ elements.  On the right
side, we first choose $j+k$ elements from the whole set.  From these
$j+k$ elements, we then choose the $k$-element set; the remainders
form the $j$-element set.}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%		PROBABILITY
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\examonly{\newpage}

\problem {\bf (5 points)} Suppose that I roll a die, but conceal the
result from you.  You then repeatedly guess at the number that I
rolled, and I will tell you whether each guess is right or wrong.  No
proofs are required for this problem.

\begin{problemparts}

\problempart {\bf (2 points)} Suppose that you guess 1, 2, 3, 4, 5,
and then 6 in that order.  What is the expected number of guesses that
you need to get the right number?

\examonly{\vspace{3in}}

\solution{
From the definition of expected value, the answer is

\begin{eqnarray*}
\frac{1}{6} \cdot (1 + 2 + 3 + 4 + 5 + 6)
	& = &	\frac{7}{2}.
\end{eqnarray*}
}

\problempart {\bf (3 points)} Suppose that you repeatedly guess
numbers in the range 1 to 6 uniformly and mutually independently at
random.  What is the expected number of guesses that you need to get
the right number?

\solution{Let the expected number of guesses be $X$.  After a wrong
guess, the expected number of guesses is the same as before.  The
rules of the game imply the following equation.

\begin{eqnarray*}
X	& = &	\frac{1}{6} \cdot 1 + \frac{5}{6} \cdot (1 + X)
\end{eqnarray*}

By solving the equation, we find that the expected number of guesses
is $X = 6$.
}

\end{problemparts}

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

\examonly{\newpage}

\problem {\bf (5 points)} A spider eats three flies a day.  Each fly
attempting to pass through his web has an even chance of becoming
entangled.  The spider eats the flies that become entangled in his web
until he fills his quota.  After his quota is filled, the spider
allows flies that become entangled to work themselves free and escape.

Wilbur the Fly is about to attempt a flight through the spider's web.
If five flies have already made the attempt today, then what is the
probability that Wilbur survives?

(Assume that the flies become entangled mutually independently.)

\solution{Among the first five flies, the number that become entangled
is either less than half ($\leq 2$) or more than half ($\geq 3$).
These two events are equally likely, since each fly has an even chance
of becoming entangled.  Therefore, the spider has an even chance of
filling his quota with the first five flies.

The probability that Wilbur survives is computed below.

\begin{eqnarray*}
\Pr(\text{fly lives})
	& = &	1 - \Pr(\text{Wilbur dies}) \\
	& = &	1 - \Pr(\text{quota unfilled} \cap \text{Wilbur entangled}) \\
	& = &	1 - \Pr(\text{quota unfilled}) \cdot
			\Pr(\text{Wilbur entangled}) \\
	& = &	1 - \frac{1}{2} \cdot \frac{1}{2} \\
	& = &	\frac{3}{4}
\end{eqnarray*}

In the first step, we switch to computing the probability of the
complementary event.  The second step uses the fact that Wilbur the
Fly dies only if the spider's quota is unfilled and the fly becomes
entangled.  The third step follows from the fact that flies become
entangled mutually independently.  The fourth step is substitution, and
the last step is simplification.}

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

\examonly{\newpage}

\problem {\bf (10 points)} Smith and Wesson are shooting at a target.
Smith's chance of hitting the target is double that of his friend
Wesson.  If they each take a shot, then the probability that at least
one of them hits the target is $\frac{1}{2}$.  What is the probability
that Wesson hits the target with a single shot?

(The event that one hits the target is independent of the event that
the other hits the target.)

\solution{Let $S$ be the event that Smith hits, and let $W$ be the
even that Wesson hits.  We are given two facts:

\begin{eqnarray*}
\Pr(S)		& = &	2 \Pr(W) \\
\Pr(S \cup W)	& = &	\frac{1}{2}
\end{eqnarray*}

Expanding the second equation using inclusion-exclusion gives:

\begin{eqnarray*}
\Pr(S) + \Pr(W) - \Pr(S \cap W)	& = &	\frac{1}{2} \\
\Pr(S) + \Pr(W) - \Pr(S) \cdot \Pr(W)	& = &	\frac{1}{2} \\
2 \Pr(W) + \Pr(W) - 2 \Pr(W) \cdot \Pr(W) & = &	\frac{1}{2}
\end{eqnarray*}

The second equation follows from independence, and the third equation
follows by substituting in the first fact listed above.  The root of
this quadratic that makes sense as a probabilty is $\frac{3}{4} -
\frac{1}{4} \sqrt{5} = 0.19\ldots$.  }

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

\examonly{\newpage}

\problem {\bf (10 points)} A box initially contains $n$ black balls.
The following procedure is repeated.  A ball is drawn from the box at
random.  If the ball is white, then it is returned to the box.  If the
ball is black, then with probability $p$ a white ball is returned to
the box and with probability $1-p$ a black ball is returned to the
box.  What is the expected number draws needed to fill the box with
white balls?

\solution{Suppose that the box contains $k$ white balls.  The
probability that a black ball is drawn and replaced by a white ball is
$\frac{n-k}{n} \cdot p$.  Therefore, the expected number of draws to
introduce one more white ball is $\frac{n}{p(n-k)}$.  By linearity
of expectation, the expected number of draws required to fill the box
with white balls is:

\begin{eqnarray*}
\sum_{k=0}^{n-1} \frac{n}{p(n-k)}
	& = &	\frac{n}{p} \cdot \sum_{k=0}^{n-1} \frac{1}{n-k} \\
	& = &	\frac{n}{p} \cdot \sum_{j=1}^n \frac{1}{j} \\
	& = &	\frac{nH_n}{p}
\end{eqnarray*}

The second step uses the substituion $j = n - k$.
}

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

\examonly{\newpage}

\problem {\bf (5 points)} The number of people that enter Filene's
Basement in the last hour before closing on Christmas Eve is a random
variable taking on an integer value in the range 0 to 100 uniformly.

Each shopper picks at least one present to buy.  After selecting each
present, a shopper is equally likely to continue shopping and to go
pay at the checkout register.  Shoppers' decisions to continue buying
are mutually independent.

The checkout clerk throws two fair, independent dice for each item and
then charges a number of dollars equal to the sum.

What is the expected total amount of money spent by these last-minute
shoppers at Filene's Basement?

\solution{Applying Wald's Theorem twice, the expected amount of money
spent is the product of the expectations of the three random variables
described in the problem.

\begin{eqnarray*}
\Ex(\text{money spent})
	& = &	\Ex(\text{num people}) \cdot
		\Ex(\text{num gifts}) \cdot
		\Ex(\text{price}) \\
	& = &	50 \cdot 2 \cdot 7 \\
	& = &	700
\end{eqnarray*}
}

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

\examonly{\newpage}

\problem {\bf (10 points)} Solve the following problems concerning
grades at MIT.

\begin{problemparts}

\problempart {\bf (5 points)} Suppose that the average GPA at MIT is
4.0.  Give a tight upper bound on the probability that a random
student's GPA is 4.5 or higher.

\examonly{\vspace{3in}}

\solution{
From Markov's Inequality,

\begin{eqnarray*}
\Pr(\text{GPA} \geq 4.5)
	& \leq &	\frac{4.0}{4.5} \\
	& = &		\frac{8}{9}.
\end{eqnarray*}
}

\problempart {\bf (5 points)} Suppose in addition that the standard
deviation of GPA's at MIT is 0.2.  Give a tight upper bound on the
probability that a random student's GPA is 4.5 or higher, taking this
new information into account.

\solution{From the one-sided Chebyshev inequality,

\begin{eqnarray*}
\Pr(\text{GPA} - 4.0 \geq 0.5)
	& \leq &	\frac{0.2^2}{0.2^2 + 0.5^2} \\
	& = &		\frac{4}{29}
\end{eqnarray*}
}

\end{problemparts}

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

\examonly{\newpage}

\problem {\bf (10 points)} A primality testing algorithm takes as
input an integer $n \geq 2$ and outputs either PRIME or COMPOSITE.
The algorithm uses random numbers in a clever way to give a much
better run-time.  An unfortunate consequence is that the algorithm
only ouputs a correct answer with probability $\frac{2}{3}$.  The
answers produced by multiple runs of the algorithm are mutually
independent.

\begin{problemparts}
\problempart {\bf (7 points)} Suppose that we run the algorithm $Q$
times.  Use the Chernoff inequality to lower bound the probability
that the most common answer is correct.  You may treat the
approximation $\ln\left(\frac{3}{2}\right) \approx \frac{2}{5}$ as an equality.

\examonly{\vspace{3.5in}}

\solution{The expected number of wrong answers is $\frac{1}{3}Q$.  Now
we apply the Chernoff bound to upper bound the probability that the
wrong answer is actually the most common answer.

\begin{eqnarray*}
\Pr\left(\text{num wrong} \geq \frac{1}{2} \cdot Q\right)
	& = &	\Pr\left(\text{num wrong} \geq
			\frac{3}{2} \cdot \Ex(\text{num wrong})\right) \\
	& \leq &	e^{-\left(\frac{3}{2}\right)
			\cdot \left(\ln \frac{3}{2} - 1 + \frac{2}{3}\right)
			\cdot \Ex(\text{num wrong})} \\
	& \approx &	e^{-\frac{1}{10} \cdot \Ex(\text{num wrong})} \\
	& = &		e^{-\frac{1}{30} Q}
\end{eqnarray*}

Consequently, the most common answer is correct with probabiliy at least

\[
1 - e^{-\frac{1}{30} Q}.
\]
}

\problempart {\bf (3 points)} How many times must the algorithm be
run to ensure that the most common answer is correct with probability
at least $1 - \frac{1}{n}$?  Give the smallest answer that you can
justify.

\solution{Suppose that we run the algorithm at least $30 \ln n$ times.
Then the probability that the most common answer is incorrect is at
most:

\begin{eqnarray*}
e^{-\frac{1}{30} \cdot 30 \ln n}
	& = &	e^{- \ln n} \\
	& = &	\frac{1}{n}
\end{eqnarray*}

Therefore, the most common answer is correct with probability at least
$1 - \frac{1}{n}$.}

\end{problemparts}

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

\examonly{\newpage}

\problem {\bf (10 points)} The superhero Bozonmann is in hot pursuit of
the archfiend Doctor Phermion.  During each minute one of three events
occurs.

\begin{itemize}

\item With probability $p$, Bozonmann pauses to recharge his powerpack,
allowing the Doctor to get one step farther ahead.

\item With probability $q$, the evil Doctor Phermion zaps his pursuer
with a gluon gun, forcing him to fall two steps back.

\item With probability $1-p-q$ our resolute hero, Bozonmann, advances a
step closer to the notorious villain.

\end{itemize}

If Bozonman comes within two steps of Phermion, then our hero can
reach out and capture his foe immediately.
\begin{problemparts}

\problempart {\bf (5 points)} Write a recurrence and base cases
describing $P_n$, the probability that Bozonmann catches Doctor
Phermion, given that they start $n$ steps apart.  Do not solve the
recurrence.

\examonly{\vspace{1.8in}}

\solution{
\begin{eqnarray*}
P_0	& = &	1 \\
P_1	& = &	1 \\
P_2	& = &	1 \\
P_n	& = &	p P_{n+1} + q P_{n+2} + (1-p-q) P_{n-1}
	\quad \quad (n > 2)
\end{eqnarray*}
}

\problempart {\bf (5 points)} Write a recurrence and base cases
describing $E_n$, the expected number of minutes until Bozonmann
catches up to the evil Doctor, given that they start $n$ steps apart.
Do not solve the recurrence.

\solution{
\begin{eqnarray*}
E_0	& = &	0 \\
E_1	& = &	0 \\
E_2	& = &	0 \\
E_n	& = &	1 + p E_{n+1} + q E_{n+2} + (1-p-q) E_{n-1}
	\quad \quad (n > 2)
\end{eqnarray*}
}

\examonly{\vspace{1.8in}}

\examonly{
\centerline{{\bf Closing Credits for 6.042}}

\bigskip

\centerline{
\begin{tabular}{rcl}
Theory Pig & {\em played by} & THEORY PIG \\
Grzzwk of Xoros 19 & {\em played by} & Yggdril of Arcturus VI
\end{tabular}
}

\vspace{0.25in}

%  Following amended in pen.

\centerline{(No stuffed animals were harmed during the production of
this course.)}
}

\end{problemparts}


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

\end{problems} \end{document}

