\documentclass[12pt,oneside]{article}

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

\begin{document}

%\examinitials{Final Exam}{May 20, 2003}
%\newcommand{\solution}[1]{}
%\newcommand{\examonly}[1]{#1}

\exam{Final Exam Solutions}{May 21, 2003}
\newcommand{\solution}[1]{\bigskip \textbf{Solution.} #1}
\newcommand{\examonly}[1]{}

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

% Topics
%
% x logic
% x graphs
% x expectation formulas
% x induction
% x sets and functions
% x state machines
% x permutations and combinations
% x pigeonhole principle
% x harmonic numbers
% x inclusion-exclusion
% x random processes
% x combinatorial proof
% x integration bounds
% x mean time to success

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

\examonly{

\setcounter{page}{0}

\vspace{0.5in}

{\bf Write your name here and on each page:} \underline{\hspace{2.5in}}

\vspace{0.2in}

Circle the name of your tutor:

\begin{center}
\begin{tabular}{ccccc}
\\
Sam Daitch & \hspace{0.5in} & Pedro Felzenszwalb & \hspace{0.5in}
	& Blaise Gassend \\ \\
Jon Jackson & & Attila Kondacs & & Min Wu
\end{tabular}
\end{center}

\vspace{0.25in}

\begin{itemize}
\item This exam is closed book.  Calculators and computers are not
allowed.

\item You may use two handwritten pages of notes.  Photocopies are not
acceptable.

\item Show your work as fully and as clearly as possible so that
partial credit may be given.

\item Write your solutions in the space provided.  If you run out of
space, use the back of the page.

\item Do not discuss this exam with students who have not yet taken
it.  Do not leave with a copy of the exam under any circumstances.
\end{itemize}

\vspace{0.25in}

\centerline{\textbf{Good luck!}}

\vspace{0.5in}

\[
\begin{array}{|c|c|c|} \hline
\text{Problem} & \text{Points} & \text{Score} \\
 \hline 1 & 16 & \\
 \hline 2 & 12 & \\
 \hline 3 & 20 & \\
 \hline 4 & 10 & \\
 \hline 5 & 10 & \\
 \hline 6 & 12 & \\
 \hline 7 & 10 & \\
 \hline 8 & 10 & \\
 \hline \text{TOTAL} & 100 & \\ \hline
\end{array}
\]
}

\begin{problems}

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

\examonly{\newpage}

\newcommand{\tf}[1]{
    \hspace{0.2in}
    \textbf{true}
    \hspace{0.2in}
    \textbf{false}
    \hspace{0.2in}
    \parbox[t]{4.6in}{#1}
    \bigskip}

\problem \pts{16} Next to each statement, circle either {\bf
true} or {\bf false}.

\begin{enumerate}

\item \tf{If an invariant holds for a state $q$ in a state machine,
then $q$ must be reachable from the start state.}

\item \tf{For every $n \in \mathbb{N}$, there exists an $m \in
\mathbb{N}$ such that:

\beqn
\sum_{k=1}^{m} \frac{1}{k^{1.01}} & > & \sum_{k=1}^{n} \frac{1}{k}
\eeqn
}

\item \tf{Every undirected graph without self-loops contains at least
two vertices with the same degree.}

\item \tf{Let $X$ be a real-valued random variable defined on a finite
sample space.  Then $\pr{X \geq \ex{X}} > 0$.}

\item \tf{Let $f : A \to B$ be a function where $A$ and $B$ are finite
sets such that $|A| > |B|$.  If $f$ is injective, then $f$ is
bijective.}

\item \tf{If $I$ is an indicator random variable, then $\ex{I^2} =
\pr{I = 1}$.}

\item \tf{Suppose that $X \rightarrow Y$ is true.  Then the number of
propositions below that are also true must be either one or three.

\[
Y \rightarrow X
\hspace{0.5in}
\neg X \rightarrow \neg Y
\hspace{0.5in}
\neg Y \rightarrow \neg X
\]
}

\item \tf{Let $X$, $Y$, and $Z$ be mutually independent events that
occur with probability $1/2$.  Then $\pr{(X \cup Y \cup Z) \cap
\overline{(X \cap Y \cap Z)}} = 1/2$.}

\end{enumerate}

\solution{
\begin{description}

\item[false] If an invariant holds for the start state, then the
invariant holds for every reachable state.  Here, there is no
assurance that the invariant holds for the start state.  Even if there
were, the invariant may also hold for some nonreachable states.

\item[false] The sum on the left converges as $m \rightarrow \infty$,
as one can verify by the integration method.  The sum is equal to the
$n$-th Harmonic number, and thus diverges as $n \rightarrow \infty$.
Thus, for sufficiently large $n$, there is no $m$ such that the
inequality holds.

\item[true] This is a restatement of problme 7 in problem set 6 in
terms of graphs.  The proof uses the pigeonhole principle.

\item[true] This amounts to saying, ``not everyone can be below
average''.

\item[false] This Pigeonhole Principle asserts that if $A$ and $B$ are
finite sets such that $|A| > |B|$, then there is no injective function
$f: A \to B$.

\item[true] If $I$ is an indicator random variable, then it takes on
only the values 0 and 1.  This implies that $I^2 = I$, since $0^2 = 0$
and $1^2 = 1$.  Therefore, $\ex{I^2} = \ex{I} = \pr{I = 1}$.  In the
last step, we use the standard fact that the expectation of an
indicator random variable is equal to the probability that the
variable is 1.

\item[true] The first two propositions are the {\em converse} and the
{\em inverse}.  These are either both true or both false.  The last
proposition is the contrapositive, which is necessarily true.

\item[true] Three are eight possibilities to consider, since each of
the events either occurs or does not occur.  The event in question
occurs in all but two cases: when $X$, $Y$, and $Z$ are all true and
when they are all false.  Thus, this event happens with probability
$6/8 = 3/4$.

\end{description}
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\examonly{\newpage}

\problem \pts{12} Recall that a {\em tournament} is a directed graph
without self-loops such that for every pair of distinct vertices $u$
and $v$, there is either an edge $u \rightarrow v$ or an edge $v
\rightarrow u$, but not both.  In a tournament, a vertex $v$ is called
an {\em emperor} if there are directed edges from $v$ to every other
vertex in the tournament.  A {\em cycle} in a tournament is a nonempty
sequence of directed edges $v_1 \rightarrow v_2$, $v_2 \rightarrow
v_3$, $v_3 \rightarrow v_4$, \ldots, $v_k \rightarrow v_1$.  A
tournament is {\em acyclic} if it has no cycles.  Use induction or
well-ordering to prove that every nonempty, acyclic tournament has an
emperor.

\solution{The proof is by induction on $n$, the number of vertices in
the tournament.  Let $P(n)$ be the proposition that if an $n$-vertex
tournament has no cycles, then it has an emperor.

There is a unique tourament with a single vertex.  It has no cycles,
but the single vertex is an emperor.  Therefore, $P(1)$ is true.

Next, we assume $P(n)$ in order to prove $P(n+1)$.  Consider a
tournament $T$ with $n+1$ vertices.  Select a vertex $v$ and remove it
from $T$ to obtain an $n$-vertex tournament $T'$.  If $T$ is acyclic,
then so is $T'$.  Therefore, $T'$ has an emperor $u$.  Now there are
two cases to consider:

\begin{itemize}

\item If there is an edge $u \rightarrow v$, then $u$ is also an
emperor of $T$, and we are done.

\item Otherwise, suppose that there is an edge $v \rightarrow u$.
Then $v$ must be an emperor of $T$.  Suppose not.  Then there is a
vertex $w$ in $T'$ and an edge $w \rightarrow v$.  However, we also
have the edge $u \rightarrow w$, since $u$ is the emperor of $T'$.
This gives the cycle $u \rightarrow w \rightarrow v \rightarrow u$ and
a contradiction.

\end{itemize}

In all cases, if $T$ is acyclic, then it has a tournament.  Therefore,
the claim follows by induction.
}


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

\examonly{\newpage}

\problem \pts{20} This problem consists of five short-answer
questions.  Your answers may contain unevaluated factorials and
binomial coefficients.  No explanations are required, but partial
credit may be awarded for work shown.

\begin{problemparts}

\problempart A five-card hand is dealt from a well-shuffled 52-card
deck.  What is the probability that the hand contains exactly three
aces?

\solution{There are $\binom{52}{5}$ hands in all.  There are
$\binom{4}{3}$ ways to select the three aces and $\binom{48}{2}$ ways
to select the remaining two cards.  This gives:

\[
\frac{\binom{52}{5}}{\binom{4}{3} \binom{48}{2}}
\]
}

\examonly{\vspace{3in}}

\problempart In a binary string, a {\em transition} is a pair of
consecutive bits that are different from one another.  How many
$n$-bit strings have exactly $k$ transitions?

\solution{There are $n-1$ positions where a transition may occur, and
we must select $k$ of these.  This gives:

\[
\binom{n-1}{k}
\]
}

\newpage

\problempart A parachute maker produces 270 parachutes, of which, in
retrospect, 13 were defective.  Assume that the parachutes were made
one at a time.  What is the largest integer $n$ such that the
parachute maker must have produced at least $n$ good parachutes in a
row?

\solution{The 13 bad parachutes are partition the $270 - 13 = 257$ good
parachutes into 14 runs.  By the pigeonhole principle, some run must
have length at least:

\beqn
\left\lceil \frac{257}{14} \right\rceil & = & 19
\eeqn
}

\examonly{\vspace{3in}}

\problempart A cube is {\em colorful} if every face is painted either
red, orange, yellow, green, blue, or violet and no two faces are
painted the same color.  Two colorful cubes are considered the same if
one can be obtained from the other by rotation.  How many different
colorful cubes are possible?

\solution{There are 5 ways to select the face opposite the red face.
The number of ways to color the remaining four faces is equal to the
number of ways to seat four people at a circular table.  In lecture,
we saw that this is $3!$.  Therefore, the number of different colorful
cubes is:

\beqn
5 \cdot 3! & = & 30
\eeqn
}

\newpage

\problempart Six couples are seated around a circular table.  The two
people in each couple must sit beside one another.  Two seatings are
considered the same if one can be obtained from the other by rotation.
How many different seating arrangements are possible?

\solution{We can arrange the couples in $5!$ ways, and then order each
of the six couples in 2 ways.  Overall, the number of possible seating
arrangements is:

\beqn
5! \cdot 2^6 & = & 5! \cdot 64
\eeqn
}

\end{problemparts}

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

\examonly{\newpage}

\problem \pts{10} Four children are playing ball: Amy, Bill, Carol,
and Stinky Peterson.  Amy has the ball initially.  Whenever a child
has the ball, he or she throws it to one of the other three children
selected uniformly and independently at random.

\begin{problemparts}

\problempart What is the expected number of throws before Stinky
Peterson touches the ball for the first time?  Justify your answer.

\examonly{\vspace{3.25in}}

\solution{With each throw, Stinky Peterson receives the ball with
probability $\frac{1}{3}$.  Therefore, the expect number of throws
before Stinky Peterson touches the ball is:

\beqn
\frac{1}{1/3} & = & 3
\eeqn
}

\problempart What is the expected number of throws before everyone has
touched the ball at least once?  Justify your answer.

\solution{Let $X_i$ be an indicator for the expected number of throws
before a total of $i$ people have touched the ball.  Since Amy has the
ball initially, we have $X_1 = 0$.  Then she throws the ball to a
second child, so $X_2 = 1$.  With each subsequent throw, the
probability that a third child receives the ball is $2/3$; therefore,
$X_3 = 1 / (2/3) = 3/2$.  Once three children have touched the ball,
each throw reaches the fourth child with probability $1/3$.
Therefore, $X_4 = 1 / (1/3) = 3$.  The expected number of throws in
total is:

\beqn
\ex{X_1 + X_2 + X_3 + X_4}
	& = &	\ex{X_1} + \ex{X_2} + \ex{X_3} + \ex{X_4} \\
	& = &	0 + 1 + \frac{3}{2} + 3 \\
	& = &	\frac{11}{2}
\eeqn
}

\end{problemparts}

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

\examonly{\newpage}

\problem \pts{10} Suppose that each edge in the graph below is colored
either red or blue uniformly and independently at random.  A {\em
simple cycle} in a graph is a sequence of distinct edges $(v_1, v_2),
(v_2, v_3), (v_3, v_4), \ldots, (v_k, v_1)$.  What is the expected
number of simple cycles that contain only blue edges?  Justify your
answer.

\bigskip
\centerline{\resizebox{!}{1.25in}{\includegraphics{final-graph.eps}}}
\bigskip

\solution{There are six possible cycles:

\begin{enumerate}
\item ABFE
\item BCGF
\item CDHG
\item ABCGFE
\item BCDFGH
\item ABCDHGFE
\end{enumerate}

\noindent Let $I_k$ be an indicator variable for the event that the
$k$-th cycle has only blue edges.  We must compute:

\beqn
\ex{\sum_{k=1}^6 I_k}
	& = &	\sum_{k=1}^6 \ex{I_k} \\
	& = &	\sum_{k=1}^6 \pr{I_k = 1} \\
	& = &	\frac{1}{2^4} + \frac{1}{2^4} + \frac{1}{2^4} +
		\frac{1}{2^6} + \frac{1}{2^6} + \frac{1}{2^8} \\
	& = &	\frac{57}{256}
\eeqn

\noindent The first step uses linearity of expectation, and the second
uses the fact that the expectation of an indicator random variable is
the probability that it is equal to 1.  For the third step, observe
that a cycle contains $n$ edges, is all blue with probability $1/2^n$.
}

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

\examonly{\newpage}

\problem \pts{12} Let $S$ be a permutation of the symbols 0, 1, 2,
\ldots, 9 selected uniformly at random.  For example, we might have:

\beqn
S & = & 2198476530
\eeqn

Justify your answers to the following questions.

\begin{problemparts}

\problempart What is the probability that $S$ contains the substring 60?

\solution{There are $10!$ permutations in all.  By regarding 60 as a
single symbol, we find that there are $9!$ permutations containing 60.
Therefore, the probability that a random permutation contains 60 is:

\beqn
\frac{9!}{10!} & = & \frac{1}{10}
\eeqn
}

\examonly{\vspace{3in}}

\problempart What is the probability that $S$ contains both the
substrings 42 and 60?

\solution{Arguing as above, there are $8!$ permutations containing
both 42 and 60.  Therefore, the probability of getting such a
permutation is:

\beqn
\frac{8!}{10!} & = & \frac{1}{90}
\eeqn
}

\examonly{\newpage}

\problempart What is the probability that $S$ contains the substrings
03 and 60?

\solution{Regarding 603 as a single symbol, we find that there are
$8!$ permutations containing both 60 and 03.  Thus, once again, the
probability is:

\beqn
\frac{8!}{10!} & = & \frac{1}{90}
\eeqn
}

\examonly{\vspace{3.5in}}

\problempart What is the probability that $S$ contains at least one of
the following substrings?

\[
60 \hspace{0.5in} 42 \hspace{0.5in} 03
\]

\solution{We use inclusion-exclusion.  The probability that $S$
contains any single substring is $1/10$ by part (a).  The probability
that $S$ contains any pair of substrings is $1/90$ by parts (b) and
(c).  Arguing much as before, the probability that $S$ contains all
three is:

\beqn
\frac{7!}{10!} & = & \frac{1}{720}
\eeqn

Putting these facts together in the inclusion-exclusion formula gives:

\beqn
3 \cdot \frac{1}{10} - 3 \cdot \frac{1}{90} + \frac{1}{720}
	& = &	\frac{193}{720}
\eeqn
}

\end{problemparts}

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

\examonly{\newpage}

\problem \pts{10} Every day, Dangerous Dan wakes up and begins his
daily ordeal:

\begin{itemize}

\item He stumbles down the front steps, taking a fatal fall with
probability $1 / 5$.

\item If he survives the steps, then he wanders across the street,
getting hit by a bus with probability $1 / 8$.

\item If he manages to avoid the bus, then he blunders into work,
where he dies of acute carpal tunnel syndrome with probability $1 /
3$.

\end{itemize}

He repeats this ordeal every day until he dies.  Dangerous Dan just
woke up.  What is the probability that the bus runs him over before he
fatally falls or types himself to death?

\solution{
A tree diagram is shown below:

\bigskip
\centerline{\resizebox{!}{2.0in}{\includegraphics{final-tree.eps}}}
\bigskip

Let $x$ be the probability of the event that Dan is killed by the bus,
starting from one of the vertices marked with an $x$.  Then we have:

\beqn
x & = & \frac{4}{5} \cdot \frac{1}{8} +
	\frac{4}{5} \cdot \frac{7}{8} \cdot \frac{2}{3} \cdot x
\eeqn

Solving this equation, we find that $x = 3/8$.
}

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

\examonly{\newpage}

\problem \pts{10} Give a combinatorial proof of the following
identity.

\beqn
\binom{4n + 1}{2n + 1}
	& = & \sum_{k=-n}^{n} \binom{2n-k}{n} \binom{2n+k}{n}
\hspace{0.6in}
\text{(for $n \in \mathbb{N}$)}
\eeqn

\solution{Both sides count the number ways to choose $2n+1$ elements
from the set $\{1, 2, \ldots, 4n+1\}$.  On the left, we have the
standard formula for the number of $(2n+1)$-combinations of a
$(4n+1)$-element set.  Alternatively, note that the median chosen
element must be in the range from $n+1$ to $3n+1$, since there must be
$n$ elements below the median and $n$ elements above.  Therefore, we
can choose $k$ so that the median chosen element is $2n-k+1$.  The $n$
smaller elements can then be chosen in $\binom{2n-k}{n}$ ways, and the
$n$ larger elements can be chosen in $\binom{2n+k}{n}$ ways.  Summing
over all the possible values of $k$ gives the expression on the right.
Since both sides count the number of elements in the same set, they
must be equal.}

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

\end{problems}
\end{document}
