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

%\hidesolutions
\showsolutions

\definecolor{lightgray}{gray}{0.8}

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

\begin{document}

\generic{Final Exam}{May 16, 2005}

\begin{center}
\textbf{YOUR NAME: } \underline{\hspace{3in}}
\end{center}

\textbf{Circle the name of your recitation instructor}:

\begin{center}
\begin{tabular}{c@{\hspace{0.5in}}c@{\hspace{0.5in}}c}
Ishan & Christos & Grant
\end{tabular}
\end{center}

\begin{itemize}

\item \textbf{This is an open-notes exam.  However, calculators are
not allowed.}

\item You may assume all results from lecture, the notes, problem
sets, and recitation.

\item Write your solutions in the space provided.  If you
need more space, write on the back of the sheet containing the
problem.

\item Be neat and write legibly.  You will be graded not only on the
correctness of your answers, but also on the clarity with which you
express them.

\item GOOD LUCK!

\end{itemize}

\vspace{0.25in}

\begin{center}
{\large
\begin{tabular}{|c|c|c|c|}
\hline
Problem & Points & Grade & Grader \\ \hline \hline
1 & 10 & & \\ \hline
2 & 15 & & \\ \hline
3 & 10 & & \\ \hline
4 & 10 & & \\ \hline
5 & 10 & & \\ \hline
6 & 15 & & \\ \hline
7 & 10 & & \\ \hline
8 & 10 & & \\ \hline
9 & 10 & & \\ \hline
Total & 100 & & \\ \hline 
\end{tabular}
}
\end{center}

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

\newpage

\begin{problem} [10 points]
Circle either \textbf{true} or \textbf{false} next to each statement
below.  Assume graphs are undirected without self-loops or
multi-edges.

\vspace{0.5in}

\begin{tabular}{rp{4.5in}@{\qquad\textbf{true}\qquad\textbf{false}}}

1. & For all $n \geq 3$, the complete graph on $n$ vertices has an Euler
tour.\\[4ex]

2. & If a graph contains no odd-length cycle, then it is bipartite.\\[4ex]

3. & Every non-bipartite graph contains a 3-cycle as a subgraph.\\[4ex]

4. & Every graph with a Hamiltonian cycle also has an Euler tour.\\[4ex]

5. & There exists a graph with 20 vertices, 10 edges, and 5 connected
components.\\[4ex]

6. & Every connected graph has a tree as a subgraph.\\[4ex]

7. & In every planar embedding of a connected planar graph, the number
of vertices plus the number of faces is greater than the number of
edges.\\[4ex]

8. & If every girl likes at least 2 boys, then every girl can be
matched with a boy she likes.\\[4ex]

9. & If every vertex in a graph has degree 3, then the graph is
4-colorable.\\[4ex]

10. & There exists a six-vertex graph with vertex degrees 0, 1, 2, 3,
4, and 5.

\end{tabular}

\end{problem}

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

\newpage

\begin{problem}[15 points]
Consider the following sequence of predicates:
%
\begin{align*}
Q_1(x_1) & = x_1 \\
Q_2(x_1, x_2) & = x_1 \implies x_2 \\
Q_3(x_1, x_2, x_3) & = (x_1 \implies x_2) \implies x_3 \\
Q_4(x_1, x_2, x_3, x_4) & = ((x_1 \implies x_2) \implies x_3) \implies x_4 \\
Q_5(x_1, x_2, x_3, x_4, x_5) & = (((x_1 \implies x_2) \implies x_3) \implies x_4) \implies x_5 \\
\ldots \qquad & \qquad \qquad \ldots
\end{align*}
%
Let $T_n$ be the number of different true/false settings of the
variables $x_1, x_2, \ldots, x_n$ for which $Q_n(x_1, x_2, \ldots,
x_n)$ is true.  For example, $T_2 = 3$ since $Q_2(x_1, x_2)$ is true
for 3 different settings of the variables $x_1$ and $x_2$:
%
\[
\begin{array}{cc|c}
x_1 & x_2 & Q_2(x_1, x_2) \\ \hline
T & T & T \\
T & F & F \\
F & T & T \\
F & F & T
\end{array}
\]

\bparts

\ppart Express $T_{n+1}$ in terms of $T_n$, assuming $n \geq 1$.

\solution[\newpage]{We have:
%
\[
Q_{n+1}(x_1, x_2, \ldots, x_{n+1})
    = Q_n(x_1, x_2, \ldots, x_n) \implies x_{n+1}
\]
%
If $x_{n+1}$ is true, then $Q_{n+1}$ is true for all $2^n$ settings of
the variables $x_1, x_2, \ldots, x_n$.  If $x_{n+1}$ is false, then
$Q_{n+1}$ is true for all settings of $x_1, x_2, \ldots, x_n$
\textit{except} for the $T_n$ settings that make $Q_n$ true.  Thus,
altogether we have:
%
\[
T_{n+1} = 2^n + 2^n - T_n = 2^{n+1} - T_n
\]
}

\ppart Use induction to prove that $T_n = \frac{1}{3}(2^{n+1} +
(-1)^n)$ for $n \geq 1$.  You may assume your answer to the previous
part without proof.

\solution{The proof is by induction.  Let $P(n)$ be the proposition
that $T_n = (2^{n+1} + (-1)^n) / 3$.

\noindent \textit{Base case:} There is a single setting of $x_1$ that
makes $Q_1(x_1) = x_1$ true, and $T_1 = (2^{1+1} + (-1)^1) / 3 = 1$.
Therefore, $P(0)$ is true.

\noindent \textit{Inductive step:} For $n \geq 0$, we assume $P(n)$
and reason as follows:
%
\begin{align*}
T_{n+1}
    & = 2^{n+1} - T_n \\
    & = 2^{n+1} - \paren{\frac{2^{n+1} + (-1)^n}{3}} \\
    & = \frac{2^{n+2} + (-1)^{n+1}}{3}
\end{align*}
%
The first step uses the result from the previous problem part, the
second uses the induction hypothesis $P(n)$, and the third is
simplification.  This implies that $P(n+1)$ is true.  By the principle
of induction, $P(n)$ is true for all $n \geq 1$.}

\eparts

\end{problem}

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

\newpage

\begin{problem}[10 points] There is no clock in my kitchen.  However:
%
\begin{itemize}
\item The faucet drips every 54 seconds after I shut off the water.
\item The toaster pops out toast every 87 seconds after I plug it in.
\end{itemize}
%
I'd like to fry an egg for exactly 141 seconds.  My plan is to plug in
the toaster and shut off the faucet at the same instant.  I'll start
frying when the faucet drips for the $D$-th time and stop frying when
the toaster pops for the $P$-th time.  What values of $D$ and $P$ make
this plan work?
%
\[
D = \fbox{\rule[-12pt]{0pt}{36pt}\rule{72pt}{0pt}} \qquad
P = \fbox{\rule[-12pt]{0pt}{36pt}\rule{72pt}{0pt}}
\]
%
\begin{center}
\textbf{Reminder:  Calculators are not allowed.}
\end{center}

\solution{The Pulverizer gives $5 \cdot 87 - 8 \cdot 54 = 3$.
Multiplying by 47 gives:
%
\begin{align*}
235 \cdot 87 - 376 \cdot 54 & = 141 \\
\implies \qquad 235 \cdot 87 & = 141 + 376 \cdot 54
\end{align*}
%
Thus, I'll start frying after at drip $D = 376$ and stop 141 seconds
later at pop $P = 87$.}

\end{problem}

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

% \ppart How many integers in the set $\set{1, 2, \ldots, 1000}$ are
% divisible by 6 or 10 or 15?

\newpage

\begin{problem}[10 points]
In the final round of the World Cup, 16 teams play a
\textit{single-elimination tournament}.
%
\begin{itemize}
\item The teams are called $A$, $B$, $C$, \ldots, $P$.
\item The tournament consists of a sequence of rounds.
\begin{itemize}
\item In each round, the teams are paired up and play matches.
\item The losers are eliminated, and the winners advance to the next
round.
\item The tournament ends when there is only one team left.
\end{itemize}
\end{itemize}
%
For example, three possible single-elimination tournaments are depicted below:

\hspace{-14pt}
\begin{picture}(464,256)
%%
%%    FIRST TOURNAMENT
%%
\put(0,0){\begin{picture}(144,256)
%\put(0,0){\dashbox(144,256){}}
%
%  first layer of teams
%
\put(8,248){\makebox(0,0){$A$}}
\put(8,232){\makebox(0,0){$B$}}
\put(8,216){\makebox(0,0){$C$}}
\put(8,200){\makebox(0,0){$D$}}
\put(8,184){\makebox(0,0){$E$}}
\put(8,168){\makebox(0,0){$F$}}
\put(8,152){\makebox(0,0){$G$}}
\put(8,136){\makebox(0,0){$H$}}
\put(8,120){\makebox(0,0){$I$}}
\put(8,104){\makebox(0,0){$J$}}
\put(8,88){\makebox(0,0){$K$}}
\put(8,72){\makebox(0,0){$L$}}
\put(8,56){\makebox(0,0){$M$}}
\put(8,40){\makebox(0,0){$N$}}
\put(8,24){\makebox(0,0){$O$}}
\put(8, 8){\makebox(0,0){$P$}}
%
%  first layer of brackets
%
\put(32,16){\line(-2,-1){16}}
\put(32,16){\line(-2,1){16}}
\put(32,48){\line(-2,-1){16}}
\put(32,48){\line(-2,1){16}}
\put(32,80){\line(-2,1){16}}
\put(32,80){\line(-2,-1){16}}
\put(32,112){\line(-2,1){16}}
\put(32,112){\line(-2,-1){16}}
\put(32,144){\line(-2,1){16}}
\put(32,144){\line(-2,-1){16}}
\put(32,176){\line(-2,1){16}}
\put(32,176){\line(-2,-1){16}}
\put(32,208){\line(-2,1){16}}
\put(32,208){\line(-2,-1){16}}
\put(32,240){\line(-2,1){16}}
\put(32,240){\line(-2,-1){16}}
%
%  second layer of teams
%
\put(40,240){\makebox(0,0){$A$}}
\put(40,208){\makebox(0,0){$C$}}
\put(40,176){\makebox(0,0){$E$}}
\put(40,144){\makebox(0,0){$G$}}
\put(40,112){\makebox(0,0){$I$}}
\put(40,80){\makebox(0,0){$K$}}
\put(40,48){\makebox(0,0){$M$}}
\put(40,16){\makebox(0,0){$O$}}
%
%  second layer of brackets
%
\put(64,32){\line(-1,-1){16}}
\put(64,32){\line(-1,1){16}}
\put(64,96){\line(-1,-1){16}}
\put(64,96){\line(-1,1){16}}
\put(64,160){\line(-1,-1){16}}
\put(64,160){\line(-1,1){16}}
\put(64,224){\line(-1,-1){16}}
\put(64,224){\line(-1,1){16}}
%
%  third layer of teams
%
\put(72,224){\makebox(0,0){$A$}}
\put(72,160){\makebox(0,0){$E$}}
\put(72,96){\makebox(0,0){$I$}}
\put(72,32){\makebox(0,0){$M$}}
%
%  third layer of brackets
%
\put(96,64){\line(-1,-2){16}}
\put(96,64){\line(-1,2){16}}
\put(96,192){\line(-1,-2){16}}
\put(96,192){\line(-1,2){16}}
%
%  fourth layer of teams
%
\put(104,192){\makebox(0,0){$A$}}
\put(104,64){\makebox(0,0){$I$}}
%
%  fourth layer of brackets
%
\put(128,128){\line(-1,-4){16}}
\put(128,128){\line(-1,4){16}}
%
%  fifth layer of teams
%
\put(136,128){\makebox(0,0){$A$}}
\end{picture}}
%%
%%    SECOND TOURNAMENT
%%
\put(160,0){\begin{picture}(144,256)
%\put(0,0){\dashbox(144,256){}}
%
%  first layer of teams
%
\put(8,248){\makebox(0,0){$B$}}
\put(8,232){\makebox(0,0){$A$}}
\put(8,216){\makebox(0,0){$C$}}
\put(8,200){\makebox(0,0){$D$}}
\put(8,184){\makebox(0,0){$G$}}
\put(8,168){\makebox(0,0){$H$}}
\put(8,152){\makebox(0,0){$F$}}
\put(8,136){\makebox(0,0){$E$}}
\put(8,120){\makebox(0,0){$P$}}
\put(8,104){\makebox(0,0){$O$}}
\put(8,88){\makebox(0,0){$N$}}
\put(8,72){\makebox(0,0){$M$}}
\put(8,56){\makebox(0,0){$L$}}
\put(8,40){\makebox(0,0){$K$}}
\put(8,24){\makebox(0,0){$J$}}
\put(8, 8){\makebox(0,0){$I$}}
%
%  first layer of brackets
%
\put(32,16){\line(-2,-1){16}}
\put(32,16){\line(-2,1){16}}
\put(32,48){\line(-2,-1){16}}
\put(32,48){\line(-2,1){16}}
\put(32,80){\line(-2,1){16}}
\put(32,80){\line(-2,-1){16}}
\put(32,112){\line(-2,1){16}}
\put(32,112){\line(-2,-1){16}}
\put(32,144){\line(-2,1){16}}
\put(32,144){\line(-2,-1){16}}
\put(32,176){\line(-2,1){16}}
\put(32,176){\line(-2,-1){16}}
\put(32,208){\line(-2,1){16}}
\put(32,208){\line(-2,-1){16}}
\put(32,240){\line(-2,1){16}}
\put(32,240){\line(-2,-1){16}}
%
%  second layer of teams
%
\put(40,240){\makebox(0,0){$A$}}
\put(40,208){\makebox(0,0){$C$}}
\put(40,176){\makebox(0,0){$G$}}
\put(40,144){\makebox(0,0){$E$}}
\put(40,112){\makebox(0,0){$O$}}
\put(40,80){\makebox(0,0){$M$}}
\put(40,48){\makebox(0,0){$K$}}
\put(40,16){\makebox(0,0){$I$}}
%
%  second layer of brackets
%
\put(64,32){\line(-1,-1){16}}
\put(64,32){\line(-1,1){16}}
\put(64,96){\line(-1,-1){16}}
\put(64,96){\line(-1,1){16}}
\put(64,160){\line(-1,-1){16}}
\put(64,160){\line(-1,1){16}}
\put(64,224){\line(-1,-1){16}}
\put(64,224){\line(-1,1){16}}
%
%  third layer of teams
%
\put(72,224){\makebox(0,0){$A$}}
\put(72,160){\makebox(0,0){$E$}}
\put(72,96){\makebox(0,0){$M$}}
\put(72,32){\makebox(0,0){$I$}}
%
%  third layer of brackets
%
\put(96,64){\line(-1,-2){16}}
\put(96,64){\line(-1,2){16}}
\put(96,192){\line(-1,-2){16}}
\put(96,192){\line(-1,2){16}}
%
%  fourth layer of teams
%
\put(104,192){\makebox(0,0){$A$}}
\put(104,64){\makebox(0,0){$I$}}
%
%  fourth layer of brackets
%
\put(128,128){\line(-1,-4){16}}
\put(128,128){\line(-1,4){16}}
%
%  fifth layer of teams
%
\put(136,128){\makebox(0,0){$A$}}
\end{picture}}
%%
%%    THIRD TOURNAMENT
%%
\put(320,0){\begin{picture}(144,256)
%\put(0,0){\dashbox(144,256){}}
%
%  first layer of teams
%
\put(8,248){\makebox(0,0){$K$}}
\put(8,232){\makebox(0,0){$C$}}
\put(8,216){\makebox(0,0){$J$}}
\put(8,200){\makebox(0,0){$D$}}
\put(8,184){\makebox(0,0){$L$}}
\put(8,168){\makebox(0,0){$B$}}
\put(8,152){\makebox(0,0){$P$}}
\put(8,136){\makebox(0,0){$I$}}
\put(8,120){\makebox(0,0){$E$}}
\put(8,104){\makebox(0,0){$F$}}
\put(8,88){\makebox(0,0){$O$}}
\put(8,72){\makebox(0,0){$A$}}
\put(8,56){\makebox(0,0){$H$}}
\put(8,40){\makebox(0,0){$G$}}
\put(8,24){\makebox(0,0){$M$}}
\put(8, 8){\makebox(0,0){$N$}}
%
%  first layer of brackets
%
\put(32,16){\line(-2,-1){16}}
\put(32,16){\line(-2,1){16}}
\put(32,48){\line(-2,-1){16}}
\put(32,48){\line(-2,1){16}}
\put(32,80){\line(-2,1){16}}
\put(32,80){\line(-2,-1){16}}
\put(32,112){\line(-2,1){16}}
\put(32,112){\line(-2,-1){16}}
\put(32,144){\line(-2,1){16}}
\put(32,144){\line(-2,-1){16}}
\put(32,176){\line(-2,1){16}}
\put(32,176){\line(-2,-1){16}}
\put(32,208){\line(-2,1){16}}
\put(32,208){\line(-2,-1){16}}
\put(32,240){\line(-2,1){16}}
\put(32,240){\line(-2,-1){16}}
%
%  second layer of teams
%
\put(40,240){\makebox(0,0){$C$}}
\put(40,208){\makebox(0,0){$D$}}
\put(40,176){\makebox(0,0){$B$}}
\put(40,144){\makebox(0,0){$P$}}
\put(40,112){\makebox(0,0){$E$}}
\put(40,80){\makebox(0,0){$A$}}
\put(40,48){\makebox(0,0){$H$}}
\put(40,16){\makebox(0,0){$M$}}
%
%  second layer of brackets
%
\put(64,32){\line(-1,-1){16}}
\put(64,32){\line(-1,1){16}}
\put(64,96){\line(-1,-1){16}}
\put(64,96){\line(-1,1){16}}
\put(64,160){\line(-1,-1){16}}
\put(64,160){\line(-1,1){16}}
\put(64,224){\line(-1,-1){16}}
\put(64,224){\line(-1,1){16}}
%
%  third layer of teams
%
\put(72,224){\makebox(0,0){$D$}}
\put(72,160){\makebox(0,0){$B$}}
\put(72,96){\makebox(0,0){$E$}}
\put(72,32){\makebox(0,0){$H$}}
%
%  third layer of brackets
%
\put(96,64){\line(-1,-2){16}}
\put(96,64){\line(-1,2){16}}
\put(96,192){\line(-1,-2){16}}
\put(96,192){\line(-1,2){16}}
%
%  fourth layer of teams
%
\put(104,192){\makebox(0,0){$B$}}
\put(104,64){\makebox(0,0){$E$}}
%
%  fourth layer of brackets
%
\put(128,128){\line(-1,-4){16}}
\put(128,128){\line(-1,4){16}}
%
%  fifth layer of teams
%
\put(136,128){\makebox(0,0){$E$}}
\end{picture}}
\end{picture}
%
Two tournaments are \textit{the same} if the same matches are played
and won by the same teams.  For example, the first and second
tournaments shown above are the same, but the third is different.  How
many \textit{different} tournaments are possible?
\end{problem}

\solution{Suppose that we draw the tournament so that the winning team
in each game is listed \textit{above} the losing team.  Then the
ordering of teams on the left completely determines all matches and
winners.  Therefore, there are $16!$ single-elimination tournaments.

Another approach is to use a result from earlier in the course: the
number of ways to pair up $2n$ people is $(2n)! / n!\ 2^n$.  In a
single-elimination tournament, we must pair up 16 teams, determine who
wins the 8 matches between them, then pair up the 8 winning teams,
detrmine who wins the 4 matches, and so forth.  The number of ways in
which this can be done is:
%
\[
\frac{16!}{8!\ 2^8} \cdot 2^8 \cdot
\frac{8!}{4!\ 2^4} \cdot 2^4 \cdot
\frac{4!}{2!\ 2^2} \cdot 2^2 \cdot
\frac{2!}{1!\ 2^1} \cdot 2^1 = 16!
\]

A final alternative is to use the General Product Rule.  The champions
can be chosen in 16 ways, the other finalists in 15 ways, the
semi-finalist that played the champions in 14 ways, the other
semi-finalist in 13 ways, and so forth.  In all, this gives $16!$
tournaments again.}

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

\newpage

\begin{problem}[10 points]
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{problem}

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

\newpage

\begin{problem}[15 points]
On the morning of day 1, I put a gray document on my desk.  This
creates a stack of height 1:
%
\begin{center}
\begin{picture}(150,56)
\fboxsep=0pt
\fboxrule=0.75pt
% \put(0,0){\dashbox(150,56){}} % bounding box
\put(150,50){\line(-1,0){150}}
\put(150,50){\line(0,-1){50}}
\put(80,53){\fcolorbox{black}{lightgray}{\rule{72pt}{0pt}\rule{0pt}{6pt}}}
\end{picture}
\end{center}
%
On each subsequent morning, I insert a white document into the stack
at a position selected uniformly at random.  For example, the stack
might look like this on the evening of day 5:
%
\begin{center}
\begin{picture}(165,100)(0,20)
\fboxsep=0pt
\fboxrule=0.75pt
% \put(0,20){\dashbox(165,100){}} % bounding box
\put(150,50){\line(-1,0){150}}
\put(150,50){\line(0,-1){30}}
\put(165,100){\vector(-1,0){10}}
\put(80,93){\fcolorbox{black}{white}{\rule{72pt}{0pt}\rule{0pt}{4pt}}}
\put(165,90){\vector(-1,0){10}}
\put(80,83){\fcolorbox{black}{lightgray}{\rule{72pt}{0pt}\rule{0pt}{4pt}}}
\put(165,80){\vector(-1,0){10}}
\put(80,73){\fcolorbox{black}{white}{\rule{72pt}{0pt}\rule{0pt}{4pt}}}
\put(165,70){\vector(-1,0){10}}
\put(80,63){\fcolorbox{black}{white}{\rule{72pt}{0pt}\rule{0pt}{4pt}}}
\put(165,60){\vector(-1,0){10}}
\put(80,53){\fcolorbox{black}{white}{\rule{72pt}{0pt}\rule{0pt}{4pt}}}
\put(165,50){\vector(-1,0){10}}
\end{picture}
\end{center}
%
Then, on the following morning, I would insert a white document at one
of the six positions indicated above with equal probability.

Let the random variable $B_n$ be the number of white documents below
the gray document on day $n$.

\bparts

\ppart Express $\pr{B_{n+1} = 0}$ in terms of $\pr{B_n = 0}$.
%
\[
\pr{B_{n+1} = 0} = \fbox{\rule[-12pt]{0pt}{36pt}\rule{216pt}{0pt}}
\]

\solution{
\[
\pr{B_{n+1} = 0} = \frac{n}{n+1} \pr{B_n = 0}
\]
}

\ppart Express $\pr{B_{n+1} = n}$ in terms of $\pr{B_n = n - 1}$.
%
\[
\pr{B_{n+1} = n} = \fbox{\rule[-12pt]{0pt}{36pt}\rule{216pt}{0pt}}
\]

\solution{
\[
\pr{B_{n+1} = n} = \frac{n}{n+1} \pr{B_n = n - 1}
\]
}

\ppart Express $\pr{B_{n+1} = k}$ in terms of $\pr{B_n = k}$ and
$\pr{B_n = k - 1}$ assuming that $0 < k < n$.
%
\[
\pr{B_{n+1} = k} = \fbox{\rule[-12pt]{0pt}{36pt}\rule{288pt}{0pt}}
\]

\solution{
\[
\pr{B_{n+1} = k} =
    \frac{n-k}{n+1} \pr{B_{n+1} = k} + 
    \frac{k}{n+1} \pr{B_{n+1} = k-1}
\]
}

\newpage

\ppart Use induction to prove that $B_n$ is uniformly distributed on
$\set{0, 1, 2, \ldots, n - 1}$.  You may assume your answers to the
preceding problem parts without justification.

\solution{We use induction.  Let $P(n)$ be the proposition that $B_n$
is uniformly distributed on the set $\set{0, 1, 2, \ldots, n - 1}$.

\noindent \textit{Base case.}  The random variable $B_1$ is always
equal to 0, so it is uniformly distributed on $\set{0}$.

\noindent \textit{Inductive step.}  Assume that the random variable
$B_n$ is uniformly distributed on the set $\set{0, 1, 2, \ldots, n-1}$
and consider the random variable $B_{n+1}$.  There are three cases:
%
\begin{align*}
\pr{B_{n+1} = 0}
    & = \frac{n}{n+1} \pr{B_n = 0} \\
    & = \frac{n}{n+1} \frac{1}{n} \tag{*} \\
    & = \frac{1}{n+1} \\
\pr{B_{n+1} = n}
    & = \frac{n}{n+1} \pr{B_n = n - 1} \\
    & = \frac{n}{n+1} \frac{1}{n} \tag{*} \\
    & = \frac{1}{n+1} \\
\pr{B_{n+1} = k}
    & = \frac{n-k}{n+1} \pr{B_{n+1} = k} + 
        \frac{k}{n+1} \pr{B_{n+1} = k-1} \\
    & = \frac{n-k}{n+1} \frac{1}{n} + 
        \frac{k}{n+1} \frac{1}{n} \tag{*} \\
    & = \frac{1}{n+1}
\end{align*}
%
In each case, the first equation comes from the preceding problem
parts.  We use the induction hypotheses on the starred lines.  The
remaining steps are simplfications.  This shows that $B_{n+1}$ is
uniformly distributed, and the claim follows from the principle of
induction.}

\eparts

\end{problem}

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

\newpage

\begin{problem}[10 points]
Bubba and Stu are shooting at a road sign.  They take shots in this
order:
%
\begin{center}
Bubba, Stu, Stu, Bubba, Bubba, Stu, Stu, Bubba, Bubba, Stu, Stu, etc.
\end{center}
%
With each shot:
%
\begin{itemize}
\item Bubba hits the sign with probability $2/5$.
\item Stu hits the sign with probability $1/4$.
\end{itemize}
%
What is the probability that Bubba hits the sign before Stu?  Assume
that hits occur mutually independently.  You must give a
\textit{closed-form} answer to receive full credit.

\solution{
\begin{align*}
\pr{\text{Bubba hits first}}
    & = \frac{2}{5}
      + \frac{3}{5} \paren{\frac{3}{4}}^2 \frac{2}{5}
      + \paren{\frac{3}{5}}^2 \paren{\frac{3}{4}}^4 \frac{2}{5}
      + \paren{\frac{3}{5}}^3 \paren{\frac{3}{4}}^6 \frac{2}{5} + \ldots \\
    & = \frac{2/5}{1 - (3/5)(3/4)^2} \\
    & = \frac{32}{53}
\end{align*}
}

\end{problem}

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

\newpage

\begin{problem}[10 points]
There are three types of men ($A$, $B$, and $C$), and three types of
women ($D$, $E$, and $F$).  Some couples are \textit{compatible} and
others are not, as indicated below:
%
\begin{center}
\begin{tabular}{rcccc}
    & $A$ & $B$ & $C$ \\
$D$ &  no & yes & yes \\
$E$ &  no &  no & yes \\
$F$ & yes &  no & no
\end{tabular}
\end{center}
%
Men and women with the personality types shown below attend a dance.
%
\begin{center}
\begin{tabular}{rccccccccc}
Men: &
\fbox{$A$} & \fbox{$A$} & \fbox{$B$} &
\fbox{$B$} & \fbox{$B$} & \fbox{$C$} & 
\fbox{$C$} & \fbox{$C$} & \fbox{$C$} \\[4ex]
Women: &
\fbox{$D$} & \fbox{$D$} & \fbox{$D$} &
\fbox{$E$} & \fbox{$F$} & \fbox{$F$} & 
\fbox{$F$} & \fbox{$F$} & \fbox{$F$}
\end{tabular}
\end{center}
%
Suppose a pairing of the women and men is selected uniformly at
random.

\bparts

\ppart What is the probability that a particular man of type $A$ is
paired with a compatible woman?

\solution[\vspace{2.5in}]{$5/9$}

\ppart What is the expected number of compatible couples?

\solution{Let $I_k$ be an indicator for the event that the $k$-th man
is paired with a compatible woman.  Then the total number of
compatible couples is:
%
\begin{align*}
\ex{I_1 + \ldots + I_9}
    & = \ex{I_1} + \ldots + \ex{I_9} \\
    & = \frac{5}{9} + \frac{5}{9} + 
        \frac{3}{9} + \frac{3}{9} + \frac{3}{9} + 
        \frac{4}{9} + \frac{4}{9} + \frac{4}{9} + \frac{4}{9} \\
    & = \frac{35}{9}
\end{align*}
}

\eparts

\end{problem}

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

\newpage

\begin{problem}[10 points]
Every Skywalker serves either the \textit{light side} or the
\textit{dark side}.
%
\begin{itemize}
\item The first Skywalker serves the dark side.
\item For $n \geq 2$, the $n$-th Skywalker serves the same side as the
$(n-1)$-st Skywalker with probability $1/4$, and the opposite side
with probability $3/4$.
\end{itemize}
%
Let $d_n$ be the probability that the $n$-th Skywalker serves the dark
side.

\bparts

\ppart Express $d_n$ with a recurrence equation and sufficient base
cases.

\solution[\vspace{3in}]{
\begin{align*}
d_1
    & = 1 \\
d_{n+1}
    & = \frac{1}{4} \cdot d_n + \frac{3}{4} \cdot (1 - d_n) \\
    & = \frac{3}{4} - \frac{1}{2} d_n
\end{align*}
}

\ppart Give a closed-form expression for $d_n$.

\solution{The characteristic equation is $x - 1/2 = 0$.  The only root
is $x = - 1/2$.  Therefore, the homogenous solution has the form $d_n
= A \cdot (-1/2)^n$.  For a particular solution, we first guess $d_n =
c$.  This is indeed a solution for $c = 1/2$.  Therefore, the complete
solution has the form $d_n = 1/2 + A \cdot (-1/2)^n$.  Since $d_1 =
1$, we must have $A = -1/2$.  Therefore:
%
\[
d_n = \frac{1}{2} + \paren{- \frac{1}{2}}^{n+1}
\]
}

\iffalse
\ppart \textbf{PROBABLY CUT} If two consecutive Skywalkers serve
opposite sides, they have a lightsaber duel.  What is the expected
number of lightsaber duels among the first $n$ Skywalkers?

\solution{There is a dual between two consecutive Skywalkers with
probability $3/4$ and there are $n-1$ pairs of consecutive Skywalkers,
so the expected number of duels is $3(n-1)/4$.}
\fi

\eparts

\end{problem}

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

\end{document}
