%
%    Coverage
%
%  180 points = 1 pt per minute
%
%  Recent
%  - 4x counting (bijections, pigeonholing, combinatorial proof)
%  - 2x generating functions
%  - basic probability
%  - conditional probability
%  - random variables
%  - expectation
%  - binomial distribution, polling
%  - random walks
%
%  Older
%  - sums, asymptotics
%  - number theory
%  - state machines
%  - recursive definition
%  - graph theory
%  - relations
%  - induction
%  - logic

\documentclass[12pt]{article}   
\usepackage{latex-macros/course}% !! use the macros

%\showsolutions	 		% !! use to force solutions & skip query
%\hidesolutions			% !! use to force no solutions & skip query

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

\newcommand{\logsol}[1]{\instatements{ \brule{0.5in}}\insolutions{ \underline{#1}}}

\instatements{
\renewcommand{\exampreamble}{	% !! renew \exampreamble 
  \textbf{Circle the name of your Tutorial Instructor}:
  \begin{center}
  \renewcommand{\arraystretch}{1.5}
  \begin{tabular}{lllll}
Ching & Christos & Grant & Paul & Zardosht
  \end{tabular}
  \end{center}
  \begin{itemize}

  \item This quiz is \textbf{closed book}, but you may have three sheets
  of paper with notes on both sides.  There are 9 problems totaling 170
  points. Total time is 180 minutes.

  \item 
  Write your solutions in the space provided.  If you need more
  space, write on the back of the sheet containing the problem.
  Please keep your entire answer to a problem on that problem's page.

  \item 
  You may assume all of the results presented in class and in the
  assigned reading.   GOOD LUCK!

\iffalse
  \item  
  \textbf{Be neat and write legibly}.  You will be graded not only on
  the correctness of your answer, but also on the clarity with which
  you express it.
\fi


  \end{itemize}}}

\begin{document} 
\final			% !! start the paper

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

\begin{examproblem}{20}
Professor Plum, Mr. Green, and Miss Scarlet are all plotting to shoot
Colonel Mustard.  If one of these three has both an
\textit{opporunity} and the \textit{revolver}, then that person shoots
Colonel Mustard.  Otherwise, Colonel Mustard escapes.

\textbf{Exactly one} of the three has an \textit{opportunity} with
the following probabilities:

\begin{align*}
\pr{\text{Plum has opportunity}} & = 1 / 6 \\
\pr{\text{Green has opportunity}} & = 2 / 6 \\
\pr{\text{Scarlet has opportunity}} & = 3 / 6
\end{align*}

\textbf{Exactly one} has the \textit{revolver} with the following
probabilities, regardless of who has an opporuntity:

\begin{align*}
\pr{\text{Plum has revolver}} & = 4 / 8 \\
\pr{\text{Green has revolver}} & = 3 / 8 \\
\pr{\text{Scarlet has revolver}} & = 1 / 8
\end{align*}

\bparts

\ppart[5] Draw a tree diagram for this problem.  Indicate edge and
outcome probabilities.

\solution[\newpage]{}

\ppart[5] What is the probability that Colonel Mustard is shot?

\solution[\vspace{2in}]{$13/48$}

\ppart[5] What is the probability that Colonel Mustard is shot, given
that Scarlet does not have the revolver?

\solution[\vspace{2in}]{$5/21$}

\ppart[5] What is the probability that Mr. Green had an opportunity,
given that Colonel Mustard was shot?

\solution{$6/13$}

\eparts

\end{examproblem}

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

\instatements{\newpage}

\begin{examproblem}{20} For the following problems, you do not need to
simplify your answers.

\bparts

\ppart[5] Next Christmas, the Grumpersons plan to divide among their
three children not only 11 pieces of coal, but also 13 pieces of scrap
metal and 3 shards of glass.  In how many different ways can this be
done?

\solution[\vspace{3in}]{There is a bijection with sequences containing
11 pieces of coal, 13 pieces of scrap metal, 3 shards of glass, and 2
``dividers''.  The number of such sequences is:

\[
\frac{(11 + 13 + 3 + 2)!}{11!\ 13!\ 3!\ 2!}
\]
}

\ppart[5] Each vertex of the graph below must be colored red, orange,
yellow, or green such that adjacent vertices are colored differently.
In how many different ways can this be done?

\bigskip
\centerline{\resizebox{!}{0.75in}{\includegraphics{color-graph}}}
\bigskip

\solution{
\[
4 \cdot 3 \cdot 2^8
\]
}

\instatements{\newpage}

\ppart[5] How many different sequences of natural numbers $(x_1,
\ldots, x_7)$ satisfy \textit{both} of the following equations:
\begin{align*}
x_1 + x_2 + x_3 & = 50 \\
x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 & = 80
\end{align*}

\solution[\vspace{2in}]{
\[
\binom{52}{2} \cdot \binom{33}{3}
\]
}

\ppart[5] Each day, an MIT student selects a breakfast from among 8
possibilities:

\bigskip
\centerline{cereal, fruit, pancakes, \ldots, Doritos}
\bigskip

The student selects lunch from among 10 possibilities:

\bigskip
\centerline{sandwich from a truck, pizza from a truck, falafel from a
truck, \ldots, Doritos}
\bigskip

The student selects dinner from among 7 possibilities:

\bigskip
\centerline{pasta, hamburger, tacos, pizza, \ldots, Doritos}
\bigskip

In how many different ways can the student select a breakfast, a
lunch, and a dinner if at most one meal can be Doritos?

\solution{
\[
8 \cdot 10 \cdot 7 - 8 \cdot 10 - 10 \cdot 7 - 8 \cdot 7 + 2
\]
}

\eparts

\end{examproblem}

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

\instatements{\newpage}

\begin{examproblem}{20}
Consider the following equation:
\begin{equation}
\label{eq:star}
\binom{2n}{n+1} = \sum_{k=0}^{n-1} \binom{n}{k} \binom{n}{k+1} \tag{*}
\end{equation}

\bparts

\ppart[5] Describe a set $S$ of binary sequences whose size is given by the
expression on the left.

\solution[\vspace{1.5in}]{
Let $S$ be all $2n$-bit sequences with exactly $n + 1$ ones.
}

\ppart[10] Describe a way of partitioning $S$ into disjoint subsets
$T_0, \ldots, T_{n-1}$ such that:
\[
\card{T_k} = \binom{n}{k} \binom{n}{k+1}
\]
In particular, state clearly which elements of $S$ are in set $T_k$
and explain why $\card{T_k}$ satisfies this equation.

\solution[\vspace{3in}]{Let $T_k$ consist of $2n$-bit sequences with
exactly $k$ zeros in the first $n$ positions.  Each such sequence has
$n - k$ ones in the first $n$ positions, and thus $k + 1$ ones in the
last $n$ positions.

There are $\binom{n}{k}$ ways to select the first $n$ bits and
$\binom{n}{k+1}$ ways to select the last $n$ bits, and so there are
$\binom{n}{k} \binom{n}{k+1}$ elements of $T_k$ in all.qyy}

\ppart[5] Assume that you answered the previous two parts correctly.
Explain why equation~\eqref{eq:star} logically follows.

\solution{Since $S$ is equal to the disjoint union $T_0 \cup \ldots
\cup T_{n-1}$, the sum rule implies:
\[
\card{S} = \card{T_0} \cup \ldots \cup \card{T_{n-1}}
\]
Substituting the results from the two preceding parts gives
equation~\eqref{eq:star}.}

\eparts

\end{examproblem}

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

\begin{examproblem}{20}

\textit{Two} roommates can decide who must scrub the bathtub by
flipping a coin.  But how can \textit{three} roommates decide?  Here
is a procedure that works, even if the coin itself is biased!

\begin{enumerate}

\item Flip the coin three times.

\item If the coin lands the same way every time, then go to step 1.

\item Otherwise, one of the three coins lands differently from the
other two; let the random variable $k$ be the number of this coin.
For example, $k(HHT) = 3$ and $k(THT) = 2$.

\end{enumerate}

Suppose that the coin lands heads-up with probability $p$, where $0 <
p < 1$, and that the results on succssive tosses are independent.

\bparts

\ppart[6] What is the probability that the branch back to step 1 is
taken?

\solution[\vspace{1.5in}]{$p^3 + (1 - p)^3$}

\ppart[7] If step 3 is reached, what is the probability that two of
the last three flips were heads?

\solution[\vspace{1.75in}]{$3 p^2 (1-p) / (1 - p^3 + (1 - p)^3)$}

\ppart[7] What is the expected number of times that the coin is flipped?

\solution{$3 / (1 - p^3 + (1 - p)^3)$}

\eparts

\end{examproblem}

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

\instatements{\newpage}

\begin{examproblem}{20}
Let $p_1, p_2, p_3, \ldots$ be the sequence of primes.  Thus:
\begin{align*}
p_1 & = 2 & p_2 & = 3 & p_3 & = 5 & p_4 & = 7 & \ldots
\end{align*}
Let $k$ be an integer selected uniformly at random from the set
$\set{1, 2, 3, \ldots, p_n!}$.  (Note the factorial symbol.)

\bparts

\ppart[4] What is the probability that $p_i \mid k$ if $1 \leq i \leq n$?

\solution[\vspace{1.25in}]{$1/p_i$}

\ppart[8] What is the expected number of primes in the set $\set{p_1,
p_2, p_3, \ldots, p_n}$ that divide $k$?  You may leave your answer as
a sum; a closed form is \textbf{not} required.

\solution[\vspace{2in}]{
$1/p_1 + 1/p_2 + \ldots + 1/p_n$
}

\ppart[8] Are the events $p_i \mid k$ and $p_{j} \mid k$ independent
or not, if $1 \leq i < j \leq n$?  Briefly justify your answer.

\solution{Yes.  We have:
\begin{align*}
\pr{p_i \mid k \cap p_j \mid k}
    & = \pr{p_i p_j \mid k} \\
    & = \frac{1}{p_i p_j} \\
    & = \pr{p_i \mid k} \cdot \pr{p_j \mid k}
\end{align*}
}

\eparts

\end{examproblem}

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

\instatements{\newpage}

\begin{examproblem}{20}
Amy and Bill say sorry to Poor Pete for cheating him in the
coin-flipping game.  To make him feel better, they offer to play a new
game:

\begin{enumerate}
\item Each player puts \$2 on the table.
\item Each player secretly writes a number between 1 and 4.
\item They roll a fair, four-sided die with faces numbered 1, 2, 3, and 4.
\item The money on the table is divided among the players that guessed
correctly.  If no one guessed correctly, then everyone gets their
money back \textit{and Poor Pete is paid a $\$0.25$ in ``apology
money''}.
\end{enumerate}

Suppose that, once again, Amy and Bill cheat by picking a pair of
\textit{distinct} numbers uniformly at random.

\bparts

\ppart[12] For each event listed below, indicate the probability of
the event and Poor Pete's profit if that event occurs.

\newcommand{\answerbox}{\fbox{\begin{minipage}{1in}\vspace{0.5 in}\hspace{1in}\end{minipage}}}

\begin{center}
\begin{tabular}{lcc}
\begin{minipage}{3in}
Pete guesses right AND \\
either Amy or Bill guesses right
\end{minipage} & \answerbox & \answerbox \\
\begin{minipage}{3in}
Pete guesses right AND \\
both Amy and Bill guess wrong
\end{minipage}& \answerbox & \answerbox \\
\begin{minipage}{3in}
Pete guesses wrong AND \\
either Amy or Bill guesses right
\end{minipage} & \answerbox & \answerbox \\
\begin{minipage}{3in}
Pete guesses wrong AND \\
both Amy and Bill guess wrong
\end{minipage} & \answerbox & \answerbox \\
\end{tabular}
\end{center}

\ppart[8] What is Poor Pete's expected profit?

\eparts

\end{examproblem}

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

\instatements{\newpage}
\begin{examproblem}{20}
We consider the unbiased Gambler's Ruin game: the gambler starts with a
$n$ dollars and has some fixed target of $T>0$ dollars, where $n$ may vary
between 0 and $T$.  The gambler makes a series of 1 dollar bets.  He wins
each individual bet with probability 1/2; if he wins a bet, his wealth
increases by 1 dollar, and if he loses a bit, his wealth decreases by 1
dollar.  He continues betting until he has 0 dollars left (he is
``ruined'') or he has $T$ dollars (he ``reaches his target'').

Let
\[
w_n \eqdef \pr{\text{the gambler reaches his target starting with $\$n$}}.
\]

\bparts
\ppart[4]\label{ra}
We know that for $T \ge n\ge 2$, the probability $w_n$ satisfies the recurrence
\[
w_n = aw_{n-1} + bw_{n-2}.
\]
Fill in the values of
$a$ \logsol{2},
$b$ \logsol{-1},
$w_0$ \logsol{0},
$w_T$ \logsol{1}.

\ppart[7] \label{rb} Let $w(x)$ be the generating function for the sequence
$w_0,w_1,w_2,\dots$ where values of $w_n$ for $n>T$ are \emph{defined}
according to the recurrence above.  Derive a closed form expression for
$w(x)$ in terms of $x$ and $w_1$.  \textbf{Note:} If you're unsure of your
answers to part~(\ref{ra}), you can use the symbols ``$a,b,w_0,w_T$''
instead of their numerical values in your formula.

\solution[\newpage]{
\[\begin{array}{ccrcrcrcrl}
w(x) & \eqdef & w_0 & + & w_1 x & + & w_2 x^2 & + & w_3x^3 & + \dots\\
-2xw(x) & \eqdef & & - & 2w_0 x & - & 2w_1 x^2 & - & 2w_2x^3 & + \dots\\
x^2w(x) & \eqdef & &   &  &  & w_0 x^2 & + & w_1x^3 & + \dots\\
\hline\\
        &        & 0 & + & w_1x & + & 0 & + & 0 & + \dots 
\end{array}\]

So
\[
w(x) = \frac{w_1x}{1-2x+x^2}.
\]
}

\ppart[1] \label{rc} Briefly explain how to use the closed form in
part~(\ref{rb}) to conclude that
\[
w(x) = \frac{A}{1-x} + \frac{B}{(1-x)^2}.
\]
for some constants $A,B$.

\solution[\vspace{3in}]{ $1-2x+x^2 = (1-x)^2$ so by partial fractions,
there must be $A,B$ such that $w(x) = w_1x/(1-x)^2 = A/(1-x) + B/(1-x)^2$.
}

\ppart[8] Use part~(\ref{rc}) and the known values of $w_0$ and $w_T$ to
derive a closed form for $w_n$.  \emph{Note:} This part does \emph{not}
depend on the values of $a$ and $b$ in part~(\ref{ra}).

\solution[\vspace{4in}]{
\begin{align*}
0 = & w_0 = w(0)= A+B\\
1 = & w_T = \text{ coeff of } x^T \text{ in } A/(1-x) + \text{ coeff of }
x^T \text{ in } B/(1-x)^2\\
& = A + B(T+1).
\end{align*}
So $A=-1/T$ and $B = 1/T$.  Now

\begin{align*}
w_n & = \text{ coeff of } x^n \text{ in } \frac{-1}{T(1-x)} + \text{ coeff of }
x^n \text{ in } \frac{1}{T(1-x)^2}\\
& = \frac{-1}{T} + \frac{n+1}{T} = \frac{n}{T}.
\end{align*}}

\eparts

\end{examproblem}


\instatements{\newpage}
\begin{examproblem}{10}
Suppose we perform $2n$ independent flips of a fair coin.

\bparts

\ppart[3] What is the number, $L_n$, of heads that is \emph{most likely}
to come up? \logsol{$n$}

\ppart[7] Derive an asymptotic ($\sim$) closed form for the probability of
flipping \emph{exactly} $L_n$ heads.

\solution[\vspace{4 in}]{
\[
\frac{1}{\sqrt{\pi n}}.
\]

We derive this closed form using Stirling's formula.
We know the probability of flipping exactly $n$ heads is
\[
\binom{2n}{n}2^{-n} = \frac{2n!}{(n!)^2} 2^{-n}
\]
Now
\begin{align*}
\frac{2n!}{(n!)^2}2^{-2n}
 & \sim \frac{\sqrt{2\pi 2n}\paren{\dfrac{2n}{e}}^{2n}}
{\paren{\sqrt{2\pi n}\paren{\dfrac{n}{e}}^{n}}^2} 2^{-2n}\\
& =  \frac{2\sqrt{\pi n}\paren{\dfrac{2n}{e}}^{2n}}
{2\pi n\paren{\dfrac{n}{e}}^{2n}}2^{-n}\\
& =  \frac{2\sqrt{\pi n}\paren{\dfrac{n}{e}}^{2n}2^{2n}}
{2\pi n\paren{\dfrac{n}{e}}^{2n}}2^{-2n}\\
& = \frac{1}{\sqrt{\pi n}}.
\end{align*}
}
\eparts

\end{examproblem}

\instatements{\newpage}

\begin{examproblem}{20}

We want to estimate the fraction, $d$, of defective silicon wafers in a
long run of wafers from a fabrication facility.  To do so, we make $n$
independent random choices of wafers from the run and test them for
defects.

\bparts

\ppart[10] \label{bina}

Explain how to use the Binomial Sampling Theorem (given below) to calculate
a near-minimal number, $n$, that will allow us to estimate $d$ within 0.005
with 98\% confidence.  Be sure to describe explicitly how to estimate $d$
and why there will be such an $n$.

\begin{theorem*} [Binomial Sampling]
Let $K_1, K_2, \dots$, be a sequence of mutually independent 0-1-valued
random variables with the same expectation, $p$, and let
\[
S_n \eqdef \sum_{i=1}^n K_i.
\]
Then, for any $\epsilon > 0$,
\begin{equation}\label{eps}
\pr{\abs{\frac{S_n}{n} - p} \geq \epsilon}
\leq 
\frac{1 - 2\epsilon}{2\epsilon} \cdot
		\frac{2^{-n (1- H((1/2) - \epsilon))}}{\sqrt{2 \pi (1/4 - \epsilon^2) n}}
\end{equation}
where
\[
H(\alpha) \eqdef - \alpha\log_2 \alpha - (1-\alpha)\log_2 (1-\alpha).
\]
\end{theorem*}

\solution[\newpage]{The estimate of $d$ will be the fraction of defective
wafers among the sample of $n$.  To find $n$, let $\epsilon = 0.005$, and
search for the smallest $n$ such that the righthand side of~\eqref{eps} is
$\leq 0.02$.  There must be such an $n$ because, for any fixed $\epsilon
\geq 0$, the righthand side expression approaches 0 as $n$ approaches
infinity.}

\ppart[10] The calculations in part~(\ref{bina}) depend on some facts about how the
$n$ wafers are chosen from the run.  Circle the true statements in the list
below.

%\renewcommand{\labelenumi}{{\normalfont (\alph{enumi})}}
\begin{itemize}

\item Given a particular wafer, the probability that it is defective is
      $d$.

\item Given a particular wafer, the probability that it is defective is 1
      or 0.

\item The probability that all $n$ randomly chosen wafers will be different
      is $\Theta(1/\sqrt{n})$.

\item The probability that the first randomly chosen wafer will be chosen a
      second time approaches one as $n$ increases.

\item All wafers in the run are equally likely to be selected as the third
      among the $n$ random choices (assuming $n \geq 3$).

\item The expectation of the indicator variable for the last wafer
      \emph{chosen} being defective is $d$.

\item The expectation of the indicator variable for the last wafer in the
      \emph{fabrication run} being defective is $d$.

\item Given that the first randomly chosen wafer was defective, the
      probability that the second one will be defective is greater than $d$.

\item It turns out that there are several different colors of wafer.
      Given that the first and second randomly chosen wafers are the same color,
      the probability that the first wafer is defective may be $< d$.

\end{itemize}

\solution{(1) is false and (2) is true, since any particular wafer is
  either defective or not. (3) is false; our analyis of the Birthday
  "paradox" implies the probability is exponentially decreasing in $n$.
  (4) true; there is a positive probability, $1/\text{length of run}$, that
  a particular wafer will be chosen on any given choice, so if we keep
  choosing, we are certain to pick each wafer an arbitrary number of
  times. (5) is true by definition of independent choice (6) is true
  because the expectation of an indicator variable is the probability that
  it equals 1. (7) is false because the last wafer in the \emph{run} is not
  random: it might always be defective.  (8) is true by definition of
  independent choice. (9) is true because, for example, it may be that a
  plurality of the wafers are red, and red wafers are less likely to be
  defective.}

\eparts

\end{examproblem}

\end{document}
