\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{\lngth}[1]{\operatorname{length}\paren{#1}}
\newcommand{\logsol}[1]{\instatements{ \brule{0.5in}}\insolutions{
    \underline{#1}}}
\newcommand{\logsoltwo}[1]{\instatements{ \brule{2in}}\insolutions{
    \underline{#1}}}

\instatements{
\renewcommand{\exampreamble}{	% !! renew \exampreamble 
  \textbf{Circle the name of your Tutorial Instructor}:
  \renewcommand{\arraystretch}{1.5}
  \begin{tabular}{cccc}
  David    & Hanson   & Jelani & Sayan
  \end{tabular}

This exam is \textbf{closed book}, but you may have a one page, two-sided
personal crib sheet.
 
There are 12 problems totaling 200 points.  Write your solutions in the
space provided, if need be running over to the back of the page.  Total
time is 180 minutes.  GOOD LUCK!  }}

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


\begin{examproblem}{15}

%F02 Q1

\textbf{Induction}

Suppose $S(n)$ is a predicate on natural numbers, $n$, and suppose
\begin{equation}\label{Sk2}
\forall k \in \naturals \; S(k) \implies S(k+2).
\end{equation}
If~(\ref{Sk2}) holds, some of the assertions below must \emph{always}
(\textbf{A}) hold, some \emph{can} (\textbf{C}) hold but not always,
and some can \emph{never} (\textbf{N}) hold.  Indicate which case
applies for each of the assertions by \textbf{circling} the correct
letter.

\begin{problemparts}

\iffalse

\problempart[3]  \hspace{.2in} {\bf A C N \hspace{.2in}} 
$\forall n \ge 0\; S(n)$ 

\solution[\vspace{0.25in}]{\textbf{C}.  The assertion means that $S$ is
always true.  So $S(k+2)$ is always true, and therefore $S(k) \implies
S(k+2)$ is always true.  So this case is possible.  But~\ref{Sk2} also
holds when $S$ is always false, so the asertion does not always hold when
\ref{Sk2} does.}

\problempart[3] \hspace{.2in} {\bf A\quad N\quad C \hspace{.2in}} $\neg{S(0)}
\land \forall n \ge 1\; S(n)$ 

\solution[\vspace{0.25in}]{\textbf{C}.  This time $S$ is false at 0, but
true everywhere else.  So $S(k) \implies S(k+2)$ still always holds
because $S(k+2)$ is still always true.  So this assertion can hold, but
not always, since~(\ref{Sk2}) can hold when $S(0)$ is true.}

\problempart[3]  \hspace{.2in} {\bf A\quad N\quad C \hspace{.2in}} 
$\forall n \ge 0\; \neg{S(n)}$

\solution[\vspace{0.25in}]{\textbf{C.}  Now $S$ is always false.  So $S(k)
\implies S(k+2)$ is always true because $S(k)$ is false.  So this case is
possible, but again does not always hold.}  \fi


\problempart[3]  \hspace{.2in} {\bf A\quad N\quad C \hspace{.2in}} 
$(\forall n \le 100\; S(n)) \land (\forall n > 100\; \neg{S(n)})$

\solution[\vspace{0.25in}]{\textbf{N}.  In this case, $S$ is true for $n$
up to 100 and false from 101 on.  So $S(99)$ is true, but $S(101)$ is
false.  That means that $S(k) \not \implies S(k+2)$ for $k = 99$.  This
case is impossible.}

\iffalse
\problempart[3] \hspace{.2in} {\bf A\quad N\quad C \hspace{.2in}} $(\forall n
\le 100\; \neg{S(n)}) \land (\forall n > 100\; S(n))$

\solution[\vspace{0.25in}]{\textbf{C}.  In this case, $S$ is false for $n$
up to 100 and true from 101 on.  So $S(k) \implies S(k+2)$ for $k \le 100$
because $S(k)$ is false, and $S(k) \implies S(k+2)$ for $k \ge 99$ because
$S(k+2)$ is true.  So this case is possible, but again does not always
hold}

\problempart[2]  \hspace{.2in} {\bf A\quad N\quad C \hspace{.2in}} 
$S(0) \implies \forall n\ S(n+2)$

\solution[\vspace{0.25in}]{\textbf{C}.  If $S(n)$ is always true this
assertion holds.  So this case is possible.  If $S(n)$ is true only for
even $n$~(\ref{Sk2}) still holds, but $S(1+2)$ is false.  So this case
does not always hold.}  \fi

\problempart[3]  \hspace{.2in} {\bf A\quad N\quad C \hspace{.2in}} 
$S(1) \implies \forall n\ S(2n+1)$

\solution[\vspace{0.25in}]{\textbf{A}.  This assertion says that if $S(1)$
holds, then $S(n)$ holds for all odd $n$.  This case is always true.}

\problempart[3]  \hspace{.2in} {\bf A\quad N\quad C \hspace{.2in}} 
$[\exists n\, S(2n)] \implies \forall n \ S(2n+2)$

\solution[\vspace{0.25in}]{\textbf{C}.  If $S(n)$ is always true, this
assertion holds.  So

this case is possible.  If $S(n)$ is true only for even $n$ greater than
4,~(\ref{Sk2}) holds, but this assertion is false.  So this case does not
always hold.}

\problempart[3]  \hspace{.2in} {\bf A\quad N\quad C \hspace{.2in}} 
$\exists n\, \exists m > n\, [S(2n) \land \neg{S(2m)}]$

\solution[\vspace{0.25in}]{\textbf{N}.  This assertion says that $S$ holds for some even
number ,$2n$, but not for some other larger even number, $2m$.  However,
if $S(2n)$ holds, we can apply~(\ref{Sk2}) $n-m$ times to conclude $S(2m)$
also holds.  This case is impossible.}

\problempart[3]  \hspace{.2in} {\bf A\quad N\quad C \hspace{.2in}} 
$[\exists n\, S(n)] \implies \forall n\, \exists m> n\, S(m)$

\solution[\vspace{0.25in}]{\textbf{A}.  This assertion says that if $S$
holds for some $n$, then for every number, there is a larger number, $m$,
for which $S$ also holds.  Since~(\ref{Sk2}) implies that if there is one
$n$ for which $S(n)$ holds, there are an infinite, increasing chain of
$k$'s for which $S(k)$ holds, this case is always true.}

\iffalse
\problempart[2]  \hspace{.2in} {\bf A\quad N\quad C \hspace{.2in}} 
$\neg{S(0)} \implies \forall n \ \neg{S(2n)}$
\fi

\end{problemparts}
\end{examproblem}

\iffalse

\instatements{\newpage}

\begin{examproblem}{15}

\textbf{Graph Isomorphism}

An \emph{intersection graph} is an undirected graph whose vertices are
sets and whose edges are specified by the rule that there is an edge between
vertices $A$ and $B$ iff $A \neq B$ and $A \intersect B \neq \emptyset$.

An \emph{incidence-set} of a graph, $G$, is the set of edges incident to
some vertex of $G$.  Let $I_G$ be the intersection graph whose vertices
are the incidence-sets of $G$.  A problem from Quiz 1 showed that if every
vertex of $G$ had degree at least 2, then $G$ was isomorphic to $I_G$.
You may assume this result.

Show that every undirected graph, $H$, is isomorphic to an intersection
graph by describing a mapping of the vertices of $H$ that is an
isomorphism to some intersection graph.  You do not have to prove that the
mapping you describe actually is an isomorphism.

\hint Let $G$ be the subgraph of $H$ obtained by ignoring the vertices of
degree less than 2.

\solution[\newpage]{By the assumed result, we know that $G$ is isomorphic
to $I_G$, so all we need to do is extend this isomorphism to include the
vertices of $H$ of degree less of than 2.  That is, we begin by mapping
each vertex of $G$ to its image vertex of $I_G$ under the isomorphism.

Then we map each degree 0 vertex, $v_0$, of $H$, to the singleton set
$\set{v_0}$.  Also, for any degree 1 vertex, $v_1$ of $H$, let $e(v_1)$ be
the unique edge incident to $v_1$, and map $v_1$ to $\set{v_1,e(v_1)}$.
Assuming wlog that no vertex is also an edge, this defines an isomorphism
from $H$ to the intersection graph whose vertices are the incidence-sets
of $G$ along with the singleton sets $\set{v_0}$ and the element-edge sets
$\set{v_1,e(v_1)}$.
}

\end{examproblem}
\fi


\instatements{\newpage}

%minor variation of fall05 Q2, prob4

\begin{examproblem}{20}
\textbf{State Machines}

We will describe a process that operates on sequences of numbers.
The process will start with a sequence that is some \emph{permutation} of
the length $6n$ sequence
\[
(1,2,\dots,n,1,2,\dots, 2n,1,2,\dots,3n).
\]
\bparts
\ppart[5]\label{start} Write a simple formula for the number of possible starting
sequences.
\solution[\vspace{1.0in}]{
Using the Bookkeeper rule: There are $6n$ occurrences of digits, where 
each digit from $1$ to $n$ appears 3 times, and each digit from $n+1$ to
$2n$ appears twice, and each digit from $2n+1$ to $3n$ appears once, so
the number of possible starting sequences is
\[
\frac{(6n)!}{(3!)^n (2!)^n} = \frac{(6n)!}{12^n}.
\]
}
\eparts

If $(s_1,\dots,s_k)$ is a sequence of numbers, then the $i$ and $j$th
elements of the sequence are \emph{out of order} if the number on the left
is strictly larger the number on the right, that is, if $i<j$ and $s_i >
s_j$.  Otherwise, the $i$th and $j$th elements are \emph{in order}.
Define $p(S) \eqdef$ the number of ``out-of-order'' pairs of 
elements in a sequence, $S$.

From the starting sequence, we carry out the following process:

(*) Pick two consecutive elements in the current sequence, say the $i$th
and $(i+1)$st.
\begin{enumerate}
\item[I.] If the elements are not in order, then \textbf{switch them} in
the sequence and repeat step (*).
\item[II.] If the elements are in order, \textbf{remove both}, resulting
in a sequence that is shorter by two.  Then pick another element and
remove it as well.  If the length of the resulting sequence is less than
three, the process is over.  Otherwise, \textbf{reverse the sequence} and
repeat step (*).
\end{enumerate}
This process can be modelled as a state machine where the states are the
sequences that appear at step (*).  

\instatements{\newpage}

\bparts

\ppart[5] Describe a simple state invariant predicate that immediately
implies that if this process halts, then the final state is the sequence
of length zero.  (Just define the invariant; you need not prove it has the
requisite properties.)


\solution[\vspace{3in}]{
The predicate $3 \divides \lngth{S}$ is an invariant of states, $S$, and
is true of the start state, so is also true of the final state, so the
length of the final state cannot be 1 or 2.
}

\ppart[10] Prove that this process always terminates by defining a
nonnegative integer valued derived variable that is strictly decreasing.
(Just define the variable, you need not prove it has these properties.)

\solution[\vspace{2in}]{
$6n^2 \cdot \lngth{S}+ p(S)$ as in the solution to Quiz 2, Problem 4.
}


\eparts
\end{examproblem}

\instatements{\newpage}

\begin{examproblem}{15}

\textbf{Equivalence Relations and Random Variables}

A random variable, $X$ is said to \emph{match} a random variable, $Y$, iff
$X$ and $Y$ are on the same sample space and $\pr{X \neq Y} = 0$.  Prove
that ``matches'' is an equivalence relation.  \hint Note that $\pr{X \neq
Z} = \pr{[X\neq Z] \intersect [X\neq Y]} + \pr{[X\neq Z] \intersect [X =
Y]}$.

\solution[\newpage]{
Since $\pr{X\neq X} = 0$, ``matches'' is reflexive.  Also, since
$\pr{X\neq Y} = \pr{Y\neq X}$, ``matches'' is symmetric.

To prove transitivity suppose $X$ matches $Y$ and $Y$ matches $Z$.

Now we use the hint.  (The hint itself follows from the fact that the
event $[X\neq z]$ is the disjoint union of the events $[X\neq Z]
\intersect [X\neq Y]$ and $[X\neq Z] \intersect [X = Y]$.)  Also,
\[
[X\neq Z] \intersect [X \neq Y] \subseteq [X\neq Y], 
\]
and
\[
[X\neq Z] \intersect [X = Y] \subseteq [Y\neq Z],
\]
so
\begin{equation}\label{XZ}
\pr{[X\neq Z]} \leq \pr{[X\neq Y]} + \pr{[Y\neq Z]}.
\end{equation}
So if $X$ matches $Y$ and $Y$ matches $Z$, then the righthand side
of~\eqref{XZ} is 0, and so $X$ matches $Z$, which proves transivity.

An alternative proof of transitivity (not using the hint), uses the fact
that if $X(s) \neq Z(s)$ at some sample point, $s$, then either $X(s)\neq
Y(s)$ or $Y(s) \neq Z(s)$.  But if $X(s)\neq Y(s)$, then $\pr{s} = 0$,
since $X$ matches $Y$.  Similarly, if $Y(s)\neq Z(s)$, then $\pr{s} = 0$,
since $Y$ matches $Z$.  So in any case, $\pr{s} = 0$.  So $\pr{X\neq Z} =
\sum_{s \in [X\neq Z]} \pr{s} = \sum_{s \in [X\neq Z]} 0 = 0$, that is, 
$X$ matches $Z$.}
\end{examproblem}

\instatements{\newpage}

\begin{examproblem}{15}
\textbf{Planarity.}

\bparts

\ppart[8] Exhibit two planar drawings of the same 5-vertex graph in which
a face in one drawing has more edges than any face in the other drawing.

\solution[\vspace{3in}]{
One drawing is a triangle with external triangles sitting on two of its
edges; the four faces are of sizes 3,3,3,5.  The other drawing is gotten
flipping one of the external triangles to be internal; the four faces are
now of sizes 3,3,4,4.
}

\ppart[7] Prove that all planar drawings of the same graph have the same
number of faces.

\solution[\vspace{2in}]{
We know that for any connected graph, $f=e+v-2$ by Euler's formula.  Since
$e$ and $v$ are uniquely determined by the graph, $f$ must also be
determined.

For a general graph, we use the generalization of Euler's formula:
$f+c=e+v-1$, where $c$ is the number of connected components of the graph.
An analogous argument works.  

No points were deducted for neglecting the general case.
}

\eparts

\end{examproblem}


\instatements{\newpage}

%from CP9f

\begin{examproblem}{15}  \textbf{Inclusion-exclusion}

A certain company wants to have security for their computer systems.  So
they have given everyone a name and password.  A length 10 word containing
each of the characters:
\begin{quote}
a, d, e, f, i, l, o, p, r, s,
\end{quote}
is called a \emph{cword}.  A password will be a cword which does not
contain any of the subwords "fails", "failed", or "drop".

Use the Inclusion-exclusion Principle to find a simple formula for
the number of passwords.

\solution{
There are $7!$ cwords that contain ``drop'', $6!$ that contain ``fails'',
and $5!$ that contain ``failed''.  There are $3!$ cwords containing both
``drop'' and ``fails''.  No cword can contain both ``fails'' and
``failed''.  The cwords containing both ``drop'' and ``failed'' come from
taking the subword ``failedrop'' and the remaining letter ``s'' in any
order, so there are $2!$ of them.  So by Inclusion-exclusion, we have the
number of cwords containing at least one of the three forbidden subwords is
\[
(7! + 6! + 5!) - (3! + 0 + 2!) + 0 = 5!(48) - 8.
\]
Among the  $10!$ cwords, the remaining ones are passwords, so the number
of passwords is
\[
10! - 5!(48) + 8 = 3,623,048.
\]
}

\end{examproblem}

\instatements{\newpage}

\begin{examproblem}{15}

\textbf{Number Theory and Induction}

\bparts

\ppart[5] Seashells are used for currency on a remote island.  However,
there are only \textit{huge} shells worth $2^{10}$ dollars and
\textit{gigantic} shells worth $3^{12}$ dollars.  Suppose islander $A$
owes $m >0$ dollars to islander $B$.  Explain why the debt can be repaid
through an exchange of shells provided $A$ and $B$ both have enough of
each kind.

\solution[\vspace{3in}]{The greatest common divisor of $2^{10}$ and $3^{12}$ is 1,
so there exist integers $x$ and $y$ such that:
%
\[
x \cdot 2^{10} + y \cdot 3^{12} = 1
\]
%
Multiplying both sides by $m$ gives:
\[
m x \cdot 2^{10} + m y \cdot 3^{12} = m
\]
%
Thus, islander $A$ can repay the debt with $m x$ huge shells and $m y$
gigantic shells.  (A positive quantity indicates that $A$ gives shells
to $B$ and a negative quantity indicates that $B$ gives shells to
$A$.)}

\ppart[10]
Give an inductive proof that the Fibonacci numbers $F_n$ and $F_{n+1}$
are relatively prime for all $n \geq 0$.  The Fibonacci numbers are
defined as follows:
\[
F_0 = 0, \qquad F_1 = 1, \qquad F_n = F_{n-1} + F_{n-2} \quad \text{(for $n \geq 2$)}.
\]

\solution{We use induction on $n$.  Let $P(n)$ be the proposition that $F_n$
and $F_{n+1}$ are relatively prime.

\noindent \textit{Base case:} $P(0)$ is true because $F_0 = 0$ and $F_1 = 1$
are relatively prime.

\noindent \textit{Inductive step:} Assume that $P(n)$ is true where $n
\geq 0$; that is, $F_n$ and $F_{n+1}$ are relatively prime.  We must
show that $F_{n+1}$ and $F_{n+2}$ are relatively prime as well.  If
$F_{n+1}$ and $F_{n+2}$ had a common divisor $d > 1$, then $d$ would
also divide the linear combination $F_{n+2} - F_{n+1} = F_n$,
contradicting the assumption that $F_n$ and $F_{n+1}$ are relatively
prime.  So $F_{n+1}$ and $F_{n+2}$ are relatively prime.

The theorem follows by induction.}

\eparts

\end{examproblem}


\instatements{\newpage}

\begin{examproblem}{20}

\textbf{Combinatorial Identities}

\bparts

\ppart[10] Give a combinatorial proof that
\begin{equation}\label{ibn}
\sum_{i=1}^n i\binom{n}{i} = n2^{n-1}
\end{equation}
for all positive integers, $n$.

\solution[\vspace{3.5in}]{Consider all the teams of one or more people
along with a designated team-leader from among a group of $n$ people.
There are $n$ ways to pick the leader directly and $2^{n-1}$ ways to pick
the remaining members of the team, for a total of $n2^{n-1}$
teams-with-leader.

Alternatively, we could pick a positive integer $i \leq n$, then a team of
$i \geq 1$ people (there are $\binom{n}{i}$ ways to do this), and then
pick a leader of the team (there are $i$ ways to do that).  So the total
number of ways to pick a team-with-leader in this way is $\sum_{i=1}^n
i\binom{n}{i}$.  Since both processes count the number of distinct
teams-with-leader, the two counts are equal.

Another way of doing this, as some students noted, is to recognize
$i\binom{n}{i}$ as the total number of 1's in all $n$-bit strings with $i$
1's in them.  Then $\sum_{i=1}^{n} i\binom{n}{i}$ is the total number of
1's in all possible n-bit binary strings.  On the other hand, since half
of the bits in the $2^{n}$ possible strings are 1's, we can conclude that
this total is simply $n2^{n}/2 = n2^{n-1}$.}

\ppart[10] Now use the fact that the expected number of heads in $n$ tosses of
a fair coin is $n/2$ to give a different proof of equation~\eqref{ibn}.

\solution[\vspace{3in}]{
\begin{align*}
\frac{n}{2} & = \expect{\text{\# Heads in $n$ fair flips}}\\
    & \eqdef \sum_{i=0}^n i \pr{\text{$i$ Head in $n$ fair flips}}\\
    & = \sum_{i=1}^n i \binom{n}{i}\paren{\frac{1}{2}}^n\\
    & = \frac{\sum_{i=1}^n i \binom{n}{i}}{2^n}.
\end{align*}
Therefore
\[
n2^{n-1} = \frac{n}{2}2^n = \sum_{i=1}^n i \binom{n}{i}.
\]
}

\eparts
\end{examproblem}

\instatements{\newpage}

\begin{examproblem}{20}

\textbf{Generating Functions}

Let $a_n$ be the number of ways to fill a box with $n$ doughnuts subject to
the following constraints: 

\begin{itemize}
\item The number of glazed doughnuts must be odd.
\item The number of chocolate doughtnuts must be a multiple of 4.
\item The number of plain doughnuts is 0 or 2.
\item The number of sugar doughnuts is at most 1.
\end{itemize}

\bparts

\ppart[8]  Write a generating function for each of the four doughnut types:
\[\begin{tabular}{ll}
$G(x) = $\logsoltwo{$x/(1-x^2)$}  & $C(x) = $\logsoltwo{$1(/1-x^4)$}
\end{tabular}\]

\[\begin{tabular}{ll}
$P(x) = $\logsoltwo{$1+x^2$}  & $S(x) = $\logsoltwo{$1+x$}
\end{tabular}\]

\iffalse
\solution{
\[\begin{array}{cc}
G(x)= \dfrac{x}{1-x^2} &  C(x) = \dfrac{1}{1-x^4}
\end{array}\]

\[\begin{array}{cc}
P(x) = 1+x^2          &  S(x) = 1+x
\end{array}\]
}\fi


\ppart[12] Derive a closed formula for $a_n$.  

\solution[\vspace{6in}]{
We have
\begin{eqnarray*}
A(x) &=& \frac{x}{(1+x)(1-x)^2} \\
     &=& \frac{-1/4}{1+x} 
         + \frac{-1/4}{1-x}
         + \frac{1/2}{(1-x)^2}
\end{eqnarray*}
by partial fractions.  This gives
\begin{align*}
a_n & = - \frac{(-1)^n}{4} - \frac{1^n}{4} + \frac{\binom{n+1}{1}}{2}\\
    & = \begin{cases}
       \frac{n}{2} & \text{if $n$ is even,}\\
       \frac{n}{2} + \frac{1}{2}  & \text{if $n$ is odd.}
        \end{cases}\\
    & = \ceil{\frac{n}{2}}.
\end{align*}
}

\eparts
\end{examproblem}

\instatements{\newpage}

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

\instatements{\newpage}

%spring05 final
\begin{examproblem}{15}

\textbf{Conditional Probability}

There are 3 children of different ages.  What is the probability that
at least two are boys, given that at least one of the two youngest
children is a boy?

Assume that each child is equally likely to be a boy or a girl and
that their genders are mutually independent.  A correct answer alone
is sufficient.  However, to be eligible for partial credit, you must
include a clearly-labeled tree diagram.

\solution{Let $M$ be the event that there are at least two boys, and
let $Y$ be the event that at least one of the two youngest children is
a boy.  In the tree diagram below, all edge probabilities are $1/2$.
%
\begin{center}
\begin{picture}(210,245)(-10,-30)
%\put(-10,-30){\dashbox(210,245){}}
\put(0,105){\line(1,2){30}}
\put(0,105){\line(1,-2){30}}
\put(30,165){\line(1,1){30}}
\put(30,165){\line(1,-1){30}}
\put(30,45){\line(1,1){30}}
\put(30,45){\line(1,-1){30}}
\put(60,15){\line(2,1){30}}
\put(60,15){\line(2,-1){30}}
\put(60,75){\line(2,1){30}}
\put(60,75){\line(2,-1){30}}
\put(60,135){\line(2,1){30}}
\put(60,135){\line(2,-1){30}}
\put(60,195){\line(2,1){30}}
\put(60,195){\line(2,-1){30}}
\put(15,155){\makebox(0,0){$B$}}
\put(15,55){\makebox(0,0){$G$}}
\put(40,65){\makebox(0,0){$B$}}
\put(40,25){\makebox(0,0){$G$}}
\put(40,185){\makebox(0,0){$B$}}
\put(40,145){\makebox(0,0){$G$}}
\put(70,30){\makebox(0,0){$B$}}
\put(70,0){\makebox(0,0){$G$}}
\put(70,90){\makebox(0,0){$B$}}
\put(70,60){\makebox(0,0){$G$}}
\put(70,150){\makebox(0,0){$B$}}
\put(70,120){\makebox(0,0){$G$}}
\put(70,210){\makebox(0,0){$B$}}
\put(70,180){\makebox(0,0){$G$}}
\put(120,-20){\makebox(0,0){$M$}}
\put(150,-20){\makebox(0,0){$Y$}}
\put(180,-20){\makebox(0,0){Prob}}
\put(120,90){\makebox(0,0){$\times$}}
\put(120,150){\makebox(0,0){$\times$}}
\put(120,180){\makebox(0,0){$\times$}}
\put(120,210){\makebox(0,0){$\times$}}
\put(150,60){\makebox(0,0){$\times$}}
\put(150,90){\makebox(0,0){$\times$}}
\put(150,120){\makebox(0,0){$\times$}}
\put(150,150){\makebox(0,0){$\times$}}
\put(150,180){\makebox(0,0){$\times$}}
\put(150,210){\makebox(0,0){$\times$}}
\put(180,0){\makebox(0,0){$1/2$}}
\put(180,30){\makebox(0,0){$1/2$}}
\put(180,60){\makebox(0,0){$1/2$}}
\put(180,90){\makebox(0,0){$1/2$}}
\put(180,120){\makebox(0,0){$1/2$}}
\put(180,150){\makebox(0,0){$1/2$}}
\put(180,180){\makebox(0,0){$1/2$}}
\put(180,210){\makebox(0,0){$1/2$}}
\put(15,-20){\makebox(0,0){youngest}}
\put(75,-20){\makebox(0,0){oldest}}
\end{picture}
\end{center}
%
\begin{align*}
\pr{M \mid Y}
    & = \frac{\pr{M \cap Y}}{\pr{Y}} \\
    & = \frac{1/2}{3/4} \\
    & = 2/3
\end{align*}
}

\end{examproblem}


\instatements{\newpage}

%From Fall 1998 ans spring 02 Final exam

\begin{examproblem}{15}

\textbf{Probability and Expectation}

A box initially contains $n$ balls, all
colored black.  A ball is drawn from the box at random.
\begin{itemize}

\item If the drawn ball is black, then a biased coin with probability,
$p>0$, of coming up heads is flipped.  If the coin comes up heads, a white
ball is put into the box; otherwise the black ball is returned to the box.

\item If the drawn ball is white, then it is returned to the box.
\end{itemize}
This process is repeated until the box contains $n$ white balls.

Let $D$ be the number of balls drawn until the process ends with the box
full of white balls.  Prove that $\expect{D} = nH_n/p$, where $H_n$ is the
$n$th Harmonic number.

\hint Let $D_i$ be the number of draws after the $i$th white ball 
until the draw when the $(i+1)$st white ball is put into the box.

\solution[\newpage]{Suppose that the box contains $k$ white balls.  The
probability that a black ball is drawn and replaced by a white ball is $p
\cdot (n-k)/n$.  Taking the placement of a white ball into the box as a
``failure,'' we know the mean time to failure is $1/(p(n-k)/n) =
n/p(n-k)$.  So $\expect{D_i}$, expected number of draws to introduce one
more white ball is $n/p(n-k)$.  By linearity of expectation, the expected
number of draws required to fill the box with white balls is:
\begin{align*}
\expect{D} & = \sum_{k=0}^{n-1} D_i\\
    & =        \sum_{k=0}^{n-1} \dfrac{n}{p(n-k)}\\
    & =    \dfrac{n}{p} \cdot \sum_{k=0}^{n-1} \dfrac{1}{n-k} \\
    & =    \dfrac{n}{p} \cdot \sum_{j=1}^n \dfrac{1}{j} & (j = n - k)\\
    & =    \dfrac{nH_n}{p}.
\end{align*}
}

\end{examproblem}


\instatements{\newpage}

\begin{examproblem}{15}

\textbf{Deviation from the Mean}

I have a randomized algorithm for calculating 6.042 grades that seems to
have very strange behavior.  For example, if I run it more than once on
the same data, it has different running times.  However, one thing I know
for sure is that its {\em expected} running time is $10$ seconds.

\bparts

\ppart[5] What does Markov's bound tell us about the probablity that my
algorithm takes longer than 1 minute ($=60$ seconds)?

\solution[\vspace{2in}]{the probability is $<1/6$}


\ppart[5] Suppose I decide to run the algorithm for 1 minute and if I
don't get an answer by that time, I stop what I am doing, and completely
restart from scratch.  Each time that I stop and restart the algorithm
gives me an independent run of the algorithm.  So, what is an upper bound
on the probability that my algorithm takes longer than 5 minutes to get an
answer?

\solution[\vspace{2in}]{$\dfrac{1}{6^5}$}

\ppart[5] Suppose some 6.042 student tells me that they determined
the {\em variance} of the running time of my algorithm, and it is 
$25$.  What is an upper bound on the probability that my algorithm
takes longer than 1 minute?

\solution{
Use Chebyshev, to get
$25/(50)^2 = 1/100$
}

\eparts
\end{examproblem}

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

\instatements{\newpage}

%revised from S04 final

\begin{examproblem}{20}

\textbf{Estimation and Confidence}

On December 20, 2005, the MIT fabrication facility produced a long run of
silicon wafers.  To estimate the fraction, $d$, of defective wafers in
this run, we will take a sample of $n$ independent random choices of
wafers from the run, test them for defects, and estimate that $d$ is
approximately the same as the fraction of defective wafers in the sample.

A calculation based on the Binomial Sampling Theorem (given below) will
yield a near-minimal number, $n_0$, and such that with a sample of size $n
= n_0$, the estimated fraction will be within 0.006 of the actual
fraction, $d$, with 97\% confidence.

\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 $1/2 > \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*}

\bparts

\ppart[10] \label{bina} Explain how to use the Binomial Sampling Theorem
to find $n_0$.  You are not expected to calculate any actual values, but
be sure to indicate which values should be plugged into what formulas.

\solution[\vspace{2in}]{To find $n_0$, let $\epsilon = 0.006$, and
search for the smallest $n$ such that the righthand side of~\eqref{eps} is
$\leq 0.03$.
}

\instatements{\newpage}

\ppart[10] The calculations in part~(\ref{bina}) depend on some facts
about the run and how the $n$ wafers in the sample are chosen.  Write T or
F next to each of the following statements to indicate whether it is True
or False.

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

\item \logsol{T} The probability that the ninth wafer in the \emph{sample} is
defective is $d$.

\solution{
The ninth wafer in the sample is equally likely to be any wafer in the
run, so the probability it is defective is the same as the fraction, $d$,
of defective wafers in the fabrication run.
}

\item \logsol{F} The probability that the ninth wafer in the \emph{run} is
defective is $d$.

\solution{
The fabrication run was completed yesterday, so there's nothing probabilistic about
the defectiveness of the ninth (or any other) wafer in the run: either it
is or it isn't defective, though we don't know which.  You could argue
that this means it is defective with probability zero or one (we don't
know which), but in any case, it certainly isn't $d$.
}


\item \logsol{T} All wafers in the run are equally likely to be selected
as the third wafer in the \emph{sample}.

\solution{The meaning of ``random choices of wafers from the
run'' is precisely that at each of the $n$ choices in the sample,
in particular at the third choice, each wafer in the run is equally likely
to be chosen.}

\item \logsol{T} The expectation of the indicator variable for the last
wafer in the \emph{sample} being defective is~$d$.

\solution{
The expectation of the indicator variable is the same as the probability
that it is 1, namely, it is the probability that the $n$th wafer chosen is
defective, which we observed in the first part of this question is $d$.
}

\item \logsol{F} Given that the first wafer in the \emph{sample} is
defective, the probability that the second wafer will also be defective is
less than than~$d$.

\solution{The meaning of ``\emph{independent} random choices of wafers
from the run'' is precisely that at each of the $n$ choices in the sample,
in particular at the second choice, each wafer in the run is equally
likely to be chosen, independent of what the first or any other choice
happened to be.}

\item \logsol{F} Given that the last wafer in the \emph{run} is defective,
the probability that the next-to-last wafer in the run will also be
defective is less than than~$d$.

\solution{As noted above, it's zero or one.}

\item \logsol{T} It turns out that there are several different colors of
wafer.  Given that the first two wafers in the sample are the same color,
the probability that the first wafer is defective may be $< d$.

\solution{ We don't know how color correlates to defectiveness.  It could
be for example, that most wafers in the run are white, and no white wafers
are defective.  Then given that two randomly chosen wafers in the sample
are the same color, their most likely color is white. This makes them less
likely to be defective than usual, that is, the conditional probability
that they will be defective would be less than $d$.}

\item \logsol{T} The probability that all the wafers in the sample will be
different is nonzero.

\solution{ We can assume the length, $r$, of the fabrication run is larger
than the sample, in which case the probability that all the wafers in the
sample are different is
\[
\frac{r}{r}\cdot \frac{r-1}{r}\cdot \frac{r-2}{r} \cdots \frac{r-(n-1)}{r}
= \frac{r!}{(r-n)!r^n} > 0.
\]
}

\item \logsol{T} The probability that all choices of wafers in the sample
will be different depends on the length of the run.

\solution{
The probability $r!/(r-n)!r^n$ depends on $r$.
}

\item \logsol{F} The probability that all choices of wafers in the sample
will be different is $\Theta(e^{-an})$ for some constant $a>0$.

\solution{
The probability is zero once the sample is larger than the run, and zero
is not $\Theta(e^{-an})$.

Note that the Birthday Principle says that the probability that all
choices of wafer are different is \emph{approximately}
\[
e^{\frac{-n(n-1)}{2r}}.
\]
But this approximation only holds when $n$ is not too close to
$r$.\footnote{It turns out that this approximation is actually pretty good
as long as $n = o(r^{2/3})$.}  But even assuming this approximation held
as $n$ grew, the bound would not be of the form $\Theta(e^{-an})$.}


\end{itemize}


\eparts

\end{examproblem}


\end{document}
