

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 1998 Final exam
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem {\bf (10 points)} The superhero Bozonmann is in hot pursuit of
the archfiend Doctor Phermion.  During each minute one of three events
occurs.

\begin{itemize}

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

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

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

\end{itemize}

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

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

\examonly{\vspace{1.8in}}

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

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

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

\examonly{\vspace{1.8in}}

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

\bigskip

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

\vspace{0.25in}

%  Following amended in pen.

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

\end{problemparts}