%  Fall '03 final exam
%
% x's indicate topics for which there is at least one problem available
%
% Primary coverage:
%   expectation
%     x linearity
%     x total expectation
%     x mean time to success
%     x natural-value formula
%       products
%       Wald
%   x markov
%   x variance
%   x chebychev
%     sampling
%     random walks
%
% Secondary coverage:
%   x logic
%     induction
%   - state machines
%   x relations
%   x graphs
%   - number theory
%   x counting

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

%\backwardscompatibility	% !! use for backwards compatibility
%\showsolutions	 		% !! use to force solutions & skip query
%\hidesolutions			% !! use to force no solutions & skip query

\instatements{
\renewcommand{\exampreamble}{	% !! renew \exampreamble 
  \textbf{Circle the name of your Tutorial Instructor}:
  \begin{center}
  \renewcommand{\arraystretch}{1.5}
  \begin{tabular}{llllll}
Ching & Edmond & Karen & Kilian & Mana & Min
  \end{tabular}
  \end{center}
  \begin{itemize}
  \item 
  This exam is \textbf{closed book}, but you may use two sheets of
  paper with notes on both sides.
  \item 
  There are fifteen problems totaling 200 points.  Total time is 170 minutes. 
  \item 
  Put your name on the top of {\bf every} page -- \emph{these
  pages may be separated for grading}.
  \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 any of the results presented in class or in the
  assigned reading.
  \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.
  \item 
  GOOD LUCK!
  \end{itemize}}}

\begin{document} 
\conflictfinal

%\final			% !! start the paper

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


\instatements{\newpage}

\begin{examproblem}{20} The following short-answer questions are independent
and can be answered in any order.

\bparts

\ppart[5] Why is the following propositional formula valid?

\[
[x \land (\neg ((\neg x) \implies y)) \land w] \implies [(u \implies
v) \lor \neg (w \land z)]
\]

(Hint:  Argue by cases according to whether $x$ is true or false.)

\solution[\vspace{3.5in}]{
If $x$ is false, then the lefthand side of the main implication is false,
and therefore the implication is true.

If $x$ is true, then $\neg x$ is false, so $((\neg x) \implies y)$ is
true, $(\neg ((\neg x) \implies y))$ is false, so again the lefthand
side of the main implication is false, and therefore the implication
is true.
}

\ppart[5] Does $2^{10}$ have a multiplicative inverse modulo $3^{11}$?
Why or why not?

\solution[\vspace{1in}] {Yes, because $2^{10}$ and $3^{11}$ are
relatively prime.}

\instatements{\newpage}
\iffalse

\ppart[4] Draw a simple graph that is acyclic, but is not a tree.

\solution[\vspace{2in}] {Two isolated vertices is the simplest
example.}
\fi

\ppart[5] Define the \emph{difference} of an ordered pair of integers $(x,
y)$ to be $x - y$.  Pick any set of 100 integers in the range 1 to 1000.
Then there are sure to be at least five different ordered pairs of numbers
from the set and all five pairs will have the same \textbf{\emph{nonzero}}
difference.  Briefly explain why.

\solution[\vspace{3in}]{There are $100^2 - 100 = 9900$ ordered pairs
with nonzero difference.  All have differences in the range -999 to
999, excluding 0.  Therefore, by the generalized pigeonhole principle,
there exist $\ceil{9900 / 1999} = 5$ pairs with the same difference.}

\ppart[5] Let $C_n$ be the number of heads obtained in $n$ independent
flips of a biased coin that comes up heads with probability $1/3$.
Describe the limiting shape of the pdf of $C_n / n$ as $n$ goes to
infinity.

\solution{The line segment from (0,0) to (1,0).}

\eparts

\end{examproblem}

\iffalse

\instatements{\newpage}

\newcommand{\tf}[1]{\item
\quad\textbf{true}\quad\textbf{false}\quad\parbox[t]{4.5in}{#1}\bigskip}

\begin{examproblem}{10}  %Eric F03

Next to each statement, circle either \textbf{true} or \textbf{false}.

\begin{enumerate}

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

\tf{$2^{10}$ has a multiplicative inverse modulo $3^{10}$.}

\tf{If a simple graph is acyclic, then it must be a tree.}

\tf{$\expect{P/Q} = \expect{P} / \expect{Q}$ if $P$ and $Q$ are
independent random variables.}

\tf{If $x$ is true, then $(\neg ((\neg x) \implies y)) \implies (u
\implies v)$ is necessarily true.}

\tf{Every set of 100 integers in the range 1 \ldots 1000 contains two
different pairs $(x, y)$ and $(x', y')$ such that $x - y = x' - y'$.}

\tf{If $X$ and $Y$ are not independent, then $\expect{X + Y} =
\expect{X} + \expect{Y}$.}

\tf{If $A$ and $B$ are events such that $A \cap B = \emptyset$, then
$A$ and $B$ are independent.}

\tf{In order for the standard deviation on this exam to be zero,
everyone must get exactly the same score.}

\end{enumerate}

\end{examproblem}
\fi

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

\instatements{\newpage}

\begin{examproblem}{10}  %S02 final

Sauron wants to conquer Middle Earth.  This project involves $n$
tasks.  Some of these tasks must be completed before others are begun.
For example, the task of {\em locating} the One Ring must precede the
task of {\em seizing} the ring.  Each task can be completed by a
horrible creature called a {\em Ringwraith} in exactly one week.  A
Ringwraith can complete multiple tasks, but can only work on one at a
time.

\bparts

\ppart[2] Sauron would like to model this scheduling problem as a
directed acyclic graph.  What should vertices represent?  When should
there be a directed edge between two vertices?

\solution[\vspace{2in}]{Each vertex corresponds to a task.  There is a
directed edge from vertex $a$ to vertex $b$ if task $a$ must preceded
task $b$.}

\ppart[3] Sauron is trying to describe various features of his
scheduling problem using standard terminology.  Next to each feature
below, write the number of the corresponding term.

\begin{center}
\textbf{Standard Terminology}\\
\begin{tabular}{rl}
1. & Transitive closure \\
2. & Topological sort \\
3. & Chain \\
4. & Antichain \\
5. & Size of the largest antichain \\
6. & Size of the smallest antichain \\
7. & Length of the longest chain \\
8. & Length of the shortest chain
\end{tabular}
\end{center}

\bigskip

\begin{tabular}{rll}
1. & \parbox[t]{5in}{
A set of tasks that can be worked on simultaneously.
} & \brule{0.5in} \\
\\
2. & \parbox[t]{5in}{
A possible order in which all the tasks could be completed, if only one
Ringwraith were available.
} & \brule{0.5in} \\
\\
3. & \parbox[t]{5in}{
The minimum number of weeks required to complete all tasks, if an
unlimited number of Ringwraiths were available.
} & \brule{0.5in}
\end{tabular}

\instatements{\newpage}

\ppart[2] Sauron discovers that conquering Middle Earth would take $t$
weeks, if he had an unlimited supply of Ringwraiths, due to the
dependencies between tasks.

If Sauron is lucky, he will be able to get by with a smallish crew of
Ringwraiths and still be able to conquer the world in $t$ weeks.  Write a
simple formula involving $n$ and $t$ for the smallest number of
Ringwraiths that could possibly be able to complete all $n$ tasks in $t$
weeks.

\solution[\vspace{3in}]{At least $\ceil{n/t}$ Ringwraiths are
necessary.  Each of the $n$ tasks must be completed in one of the $t$
weeks.  Thus, by the pigeonhole principle, at least $\ceil{n/t}$ must
be completed in some week.  But that would require at least
$\ceil{n/t}$ Ringwraiths.

This bound is the best possible.  If there is a chain of $t$ tasks and
the remaining tasks have no dependencies, then $\ceil{n/t}$
Ringwraiths are sufficient.}

\ppart[3] On the other hand, if Sauron is unlucky, he may need a large
crew of Ringwraiths in order to conquer Middle Earth in $t$ weeks.  Write
a simple formula involving $n$ and $t$ for the largest number of
Ringwraiths that Suaron would need in order to be sure of completing all
$n$ tasks in $t$ weeks -- no matter how unlucky he was.

\solution{Up to $n - t + 1$ Ringwraiths may be necessary.  This is the
case is, for example, if there is an antichain of $n - t + 1$ tasks
that can not be started until a chain of $t - 1$ tasks is completed.

Again, this bound is the best possible.  If more than $n - t + 1$
tasks are completed in one week, then there must be a week when no
tasks are completed.  If this is the case, then all the tasks can be
completed in fewer than $t$ weeks, contradicting the assumption.}

\eparts

\end{examproblem}

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

\instatements{\newpage}

\begin{examproblem}{15}\label{Zakim}   %S02 Final

The Massachusetts Turnpike Authority has a new policy for traffic control
on the Zakim bridge.  The bridge will be one way; cars will pay tolls both
on entering and exiting the bridge, but the tolls will be different.  In
particular, a car will pay \$5 to enter onto the bridge and will pay \$3 to
exit.  To be sure that there are never too many cars on the bridge, the
Authority will let a car onto the bridge only if \emph{the difference
between the amount of money currently at the entry toll booth minus the
amount at the exit toll booth is strictly less than~\$2500}.

The Authority has asked their engineering consultants to verify that this
policy will keep the number of cars from exceeding 500.  The consultants
have decided to model this scenario with a state machine whose states are
triples of natural numbers, $(A,B,C)$, where
\begin{itemize}
\item $A$ is an amount of money at the entry booth,
\item $B$ is an amount of money at the exit booth, and
\item $C$ is a number of cars on the bridge.
\end{itemize}
Any state with $C>500$ is called a \emph{collapsed} state, which the
Authority dearly hopes to avoid.  There will be no transition out of a
collapsed state.

Since the toll booth collectors may need to start off with some amount of
money in order to make change, and there may also be some number of
``official'' cars already on the bridge when it is opened to the public,
the consultants must be ready to analyze the system started at \emph{any}
state, not necessarily with a start state $(0,0,0)$.  (However, you should
assume that even official cars pay tolls when the system is running.)

\begin{problemparts}
\problempart[3] Give a mathematical model of the Authority's system for
letting cars on and off the bridge by specifying a transition relation
between states of the form $(A,B,C)$ above.  

\solution{
State $(A,B,C)$ goes to state
\begin{enumerate}
\item[(i)]
$(A+5,B,C+1)$, providing that $A-B<2500$ and $C < 500$.  This transition models
the case where a car enters the bridge.

\item[(ii)] $(A,B+3,C-1)$, providing that $0 < C \leq 500$.  This
transition models the case where a car leaves the bridge.

\end{enumerate}
}
 
\instatements{\vfill\pagebreak}


\problempart[5]\label{variables}
Characterize each of the following derived variables
\[
\renewcommand{\arraystretch}{2}
\begin{array}{|c|c|} \hline
%%A  		  & WI \\\hline 
B                 & WI \\\hline 
A+B 		  & SI \\\hline
%A-B 		  & \\\hline % N
5C-A              & \\\hline % WD
3 A - 5 B	  & \\\hline % N
B+3C              & \\\hline % WI
15C-3A + 5B       & \\\hline %C
A - 4C -B         & \\\hline %SI
\end{array}
\]
as one of the following
\begin{center}
\begin{tabular}{|ll|} \hline
constant              & C  \\  
strictly increasing   & SI \\
strictly decreasing   & SD \\
weakly increasing but not constant & WI \\
weakly decreasing but not constant & WD \\
none of the above     & N  \\\hline
\end{tabular}
\end{center}
by entering the corresponding letter-code next to the variable.

\solution{In every transition, at least one of $A$ and $B$ increases. So
their sum is strictly increasing.  $3A-5B$ can fluctuate, going up on (i)
and down on (ii).

The difference $5C-A$ doesn't change under transitions of type~(i), but
decreases under transitions of type~(ii); so is weakly decreasing.
Likewise, $B+3C$ doesn't change under transitions of type~(ii), but
increases under transitions of type~(i); so is weakly increasing.

On the other hand, $15C$ and $3A-5B$ simultaneously increase by 15 under
transition (i) or simultaneously decrease by 15 under transition (ii),
which makes their difference constant.

Finally, under (i), $A$ increases by 5, $B$ is unchanged, and $4C$
increases by 4, so $A-4C-B$ increases by $5-4 =1$.  Similarly, under (ii),
$A$ is unchanged, $4C$ decreases by 4 and $B$ increases by 3, so $A-4C-B$
increases by $-(-4) - 3 = 1$.

The completed table follows.
\[
\renewcommand{\arraystretch}{2}
\begin{array}{|c|c|} \hline
%%A  		  & WI \\\hline 
B                 & WI \\\hline 
A+B 		  & SI \\\hline 
%A-B 		  & N  \\\hline 
5C-A              & WD \\\hline
3 A - 5 B	  & N \\\hline 
B+3C              & WI \\\hline 
15C-3A + 5B       & C  \\\hline
A - 4C -B  & SI \\\hline
\end{array}
\]}

\problempart[7] Define a simple Invariant, $P$, of the transition
system which is satisfied by the state $(0,0,0)$ and is not satisfied
by any collapsed state.  That is, $P$ is a predicate on states that is
preserved by transitions from {\em any} state to another. In addition,
$P(0,0,0)$ is true, and $P(A,B,C)$ is not true whenever $C>500$.

No proof is required.

\instatements{\newpage}

\solution{
Invariant: $3A - 5B = 15C \land C \leq 500$.

The invariant obviously holds at the state $(0,0,0)$ and does not hold in
any collapsed state.  To verify the Invariant, assume $(A,B,C)$ satisfies
the Invariant and has a transition to $(A',B',C')$.  We check that
$(A',B',C')$ satisfies the Invariant by considering the two kinds of
transitions.

Transition (i) (a car enters the bridge): so
\[
15C' = 15(C + 1) = 15C + 15 = 3A -  5B + 15 = 3(A+5) - 5B = 3A' - 5B'
\]
The transition is possible only if $A-B < 2500$.  But this
implies
\[
15C = 3A -  5B \leq 3(A-B) < 7500,
\]
so $C' = C+1 < 7500/15 + 1 = 501$ and so $C' \leq 500$, as required.

Transition (ii) (a car leaves the bridge): so
\[
15C' = 15(C - 1) = 15C - 15= 3A-5B - 15 = 3A - 5(B+3) = 3A' - 5B'.
\]
In addition, $C' < C \leq 500$ so $C' \leq 500$.
}

\iffalse

\problempart[5] A clever MIT intern working for the Turnpike Authority
agrees that when the system starts in state $(0,0,0)$ the Turnpike's
bridge management policy will be \emph{safe}: the bridge will not
collapse.  But she warns her boss that the policy makes system
\emph{deadlock} inevitable, that is, traffic will eventually be unable to
move even though the bridge has not collapsed.  Explain more precisely in
terms of system transitions what the intern means, and briefly, but
clearly, justify her claim.

\solution{The interns means that any sequence of transitions starting from
$(0,0,0)$ will arrive at a state in which no transition is possible, even
though there are no cars on the bridge.  This happens because every time a
car enters and then exits the bridge the value of $A-B$ increases by 2.
So after 1250 cars have entered the bridge, no further car can enter the
bridge because $A-B\geq 2500$; after that, cars can only exit the bridge.
So in exactly 2500 transitions, the system deadlocks with the bridge empty
and no cars allowed on.  In fact, deadlock inevitably occurs starting from
\emph{any} state, unless the bridge collapses first.}

\fi


\iffalse

Let $D$ be the derived variable
\[
D \eqdef
\begin{cases}
2500 - A + B + 4C &\text{ if there is a transition from state $(A,B,C)$},\\
0 & \text{otherwise}.
\end{cases}     
Prove that $D$ is a strictly decreasing, natural number-valued variable.
In your proof, you may not assume any of the properties you designated in
part~(\ref{variables}) unless you prove them too.

\solution{
We gave a proof in part~(\ref{variables}) that $(A - 4C - B)$ is strictly
increasing.  Hence , $D = 2500 - A + B + 4C$ is strictly decreasing.  So all
that remains is showing that it is nonnegative.

But there is a transition from $(A,B,C)$ only if $

In part (b), we proved that if the bridge is standing, then it will
never collpse.  Therefore, $C \leq 500$ or $2C \leq 1000$.  Since $A - 2C - B$ 
is strictly increasing by 1 at each transition, $A - 2C - B$
will exceed 2500 after at most $(2500 + 1000 +
|Initial-value(A-2C-B)|)$ number of transitions.

Therefore,  $3500 + |Initial-value(A-2C-B)|-(A-2C-B)$ is nonnegative.

}

\problempart[0]

Prove that the system deadlocks (i.e. the bridge has fewer than 500
cars but no car can enter) regardless of what initial state it takes
(if it doesn't collapse first).

\solution{

The derived variable $D$ is a strictly decreasing integer-valued and
non-negative variable.  Eventually it will reach a minimum where it
can no longer decrease which implies termination.  No transition is
possible and the system deadlocks.

%We define a new derived variable $K-(A-2C-B)$, where K is $2500 +
%1000 + |Initial-value(A-2C-B)|$

%In part (b), we proved that if the bridge is standing, then it will
%never collpse.  Therefore, $C \leq 500$ or $2C \leq 1000$.  Since $A - 2C - B$ 
%is strictly increasing by 1 at each transition, $A - 2C - B$
%will exceed 2500 after at most $(2500 + 1000 +
%|Initial-value(A-2C-B)|) = K$

%Therefore,  $K-(A-2C-B)$ is nonnegative.

%Additionally, since $(A-2C-B)$ is strictly increasing by 1 at each
%transition, $K-(A-2C-B)$ must be strictly decreasing integer-valued.

}
\fi


\instatements{\newpage}

\instatements{\vfill\pagebreak}

\end{problemparts}
\end{examproblem}

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

\instatements{\newpage}

\begin{examproblem}{10}  %F01 final

A couple wants to borrow $d$ dollars so that they can purchase a 
new condo.  At the end of each year for the next $n$ years, one of them
will drop by the bank to make a payment on the loan.  The banker will
immediately invest this returned money at an $r$\% annual rate of
return.  The banker wants to wind up with at least as much money as a result
of the couple's payments as he would if he had invested the whole $d$
dollars at $r$\% for $n$ years starting today.

Write a closed form formula in $d,n$ and $r$ for the least annual payment
the banker might ask from the couple.

\solution[\vspace{3.5in}]{Let $R \eqdef (1+r/100)$, so that after 1 year, a
one dollar investment is worth $R$ dollars.  The banker will require that
\begin{equation*}
p \geq \frac{dR^{n}(R-1)}{R^n - 1}.
\end{equation*}
We derive this bound as follows:

Suppose that Theory Pig pays $p$ dollars at the end of each year.  The
banker can invest the first payment for $n-1$ years, the second payment
for $n-2$ years, etc., so that after $n$ years his total cash is:

\begin{eqnarray*}
\sum_{i=1}^{n} p \cdot R^{i-1}
& = & \sum_{i=0}^{n-1} p \cdot R^i\\
& = & p \frac{R^n - 1}{R - 1}.
\end{eqnarray*}

On the other hand, if the banker could invested the $d$ dollars today, then
after $n$ years his total cash is $d R^{n}$.  The first amount must
be at least as large as this, so

\begin{eqnarray*}
p \frac{R^n - 1}{R - 1} & \geq & dR^{n}\\
p &\geq& \frac{dR^{n}(R-1)}{R^n - 1}.
\end{eqnarray*}
}

\end{examproblem}

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

\instatements{\newpage}

\begin{examproblem}{10}  %F01 final

\newcommand{\spc}{\hspace{0.5in}}
\newcommand{\apart}[1]{\vspace{0.2in}
    \ppart[1]\ \ \parbox[t]{4.5in}{#1}\hfill\brule{0.75in}}

Here are the solutions to the next 10 problem parts, in no particular
order.

\[
n^m \spc m^n \spc \frac{n!}{(n-m)!} \spc
\binom{n-1+m}{m} \spc \binom{n-1+m}{n} \spc 2^{mn}
\]

\bparts

\apart{How many ways are there to put $m$ indistinguishable
balls into $n$ distinguishable urns?}

\solution{This is equal to the number of sequences with $m$ stars and
$n - 1$ bars, which is $\binom{n - 1 + m}{m}$.}

\apart{How many ways are there to put $m$ distinguishable balls into
$n$ distinguishable urns?}

\apart{How many solutions over the natural numbers are there to the
equation $x_1 + x_2 + \ldots + x_n = m$?}

\apart{How many $\sqrt{n} \times \sqrt{n}$ matrices are there with
entries drawn from $\set{1, 2, \ldots, m}$?}

\apart{How many different subsets of the set $A \times B$ are there,
if $|A| = m$ and $|B| = n$?}

\apart{How many functions are there from set $A$ to set $B$, if $|A| =
n$ and $|B| = m$?}

\apart{How many $m$-letter words can be formed from an $n$-letter \\
alphabet, if no letter is used more than once?}

\apart{How many $m$-letter words can be formed from an $n$-letter \\
alphabet, if letters can be reused?}

\apart{How many relations are there from set $A$ to set $B$, where
$|A| = m$ and $|B| = n$?}

\apart{How many injections are there from set $A$ to set $B$, where
$|A| = m$ and $|B| = n$?}

\eparts

\end{examproblem}

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

\instatements{\newpage}

\begin{examproblem}{10}  %S02 Final & spring99 final problem 7

We consider a hypothetical Institute with only two departments: EECS
and Math, and consider the experiment where we pick a random applicant
for admission to one of these departments.  Define the following
events:
\begin{eqnarray*}
A & \eqdef & \text{applicant is accepted,}\\
F & \eqdef & \text{applicant is female,}\\
M & \eqdef &  \text{applicant is male,}\\
\mathit{MATH} & \eqdef & \text{applicant applied to Math,}\\
\mathit{EECS} & \eqdef & \text{applicant applied to EECS.}
\end{eqnarray*}
Assume that all applicants are either male or female, and that no
applicant applied to both departments.
\iffalse
That is, the events $F_{EECS}$,
$F_{CS}$, $\mbox{M-EECS}$, and $\mbox{M-CS}$ are all disjoint.
\fi

\begin{problemparts}

\problempart[5] The Institute is sued for gender discrimination, with
the plaintiff observing that in both EECS and Math, the probability that a
woman is accepted is less than the probability that a man is accepted.
This observation can be precisely expressed with two inequalities
between conditional probabilities involving the events above.  State these
inequalities.

\solution[\vspace*{5cm}]{
\begin{eqnarray*}
\pr{A \mid F \intersect \mathit{EECS}} & < & \pr{A \mid M \intersect \mathit{EECS}}, \\
\pr{A \mid F \intersect \mathit{MATH}} & < & \pr{A \mid M \intersect \mathit{MATH}}.
\end{eqnarray*}
}

\problempart[5] The Institute's defense attorneys retort that overall among
all applicants, a woman is {\em more} likely to be accepted than a man.
Express this observation as an inequality between conditional probabilities
involving the events above.

\solution[\vspace*{4cm}]{
\begin{eqnarray*}
\pr{A \mid F} & > & \pr{A \mid M}
\end{eqnarray*}
}

\iffalse
\problempart Although the assertions above may appear to be logically
inconsistent, both the plaintiff's and the defense's claims about the
conditional probabilities can be correct. (Never mind whose interpretation
of the data we find more persuasive.)  Fill in the missing table entries
below with possible applicant statistics for which both the plaintiff and
the University attorneys' assertions are true.

\begin{center}
\renewcommand{\arraystretch}{.3}
\begin{tabular}{|c|c|c|c|}
\hline
& &\hspace*{1in}&\\
     & Applied & Accepted & percent accepted\\
 & & & \\ \hline \hline & & &\\
Dept & Females & Females &  Females\\
& & & \\ \hline & & &\\
Math & & & \\ & & & \\ \hline & & &\\
EECS & 100 & 70 & 70\% \\ & & & \\ \hline & & &\\
Total & &  & \\ & & &\\ \hline \hline & & &\\
Dept & Males & Males & Males\\
& & & \\ \hline & & &\\
Math & 100 & 50 & 50\% \\ & & & \\ \hline & & &\\
EECS & & & \\ & & & \\ \hline & & &\\
Total & &  & \\
& & &\\
\hline
\end{tabular}
\end{center}

\solution{
\[
\begin{array}{ccr}
\mbox{CS} & \mbox{0 females accepted, 1 applied} & 0\% \\
          & \mbox{50 males accepted, 100 applied} & 50\% \\
\mbox{EECS} & \mbox{70 females accepted, 100 applied} & 70\% \\
          & \mbox{1 male accepted, 1 applied} & 100\% \\
\hline
\mbox{Overall} & \mbox{70 females accepted, 101 applied} & \approx 70\% \\
          & \mbox{51 males accepted, 101 applied} & \approx 51\%
\end{array}
\]
}
\fi
\end{problemparts}

\end{examproblem}

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

\instatements{\newpage}

\begin{examproblem}{15}  %Eric F03

Let $\mathcal{S}$ be the set $\set{a, b, c}$.  Suppose that we construct a
binary relation $R$ on $\mathcal{S}$ with a randomized procedure.  In
particular, for each $x, y \in \mathcal{S}$, the relation $xRy$ holds with
probability $p$ and fails to hold with probability $q \eqdef 1-p$ mutually
independently.  \iffalse So, for example, the probability that $bRc$ is
the only pair of $R$-related elements is $pq^8$.\fi  Write formulas in
terms of $p$ and $q$ for the probability of each of the following events.

A correct answer gets full credit, but you can get partial credit only if
you include an explanation with your answer.

\bparts

\ppart[2] $R$ is reflexive.

\solution[\vspace{3.5in}]{$R$ is reflexive if and only if $aRa$, $bRb$,
and $cRc$ all hold.  Since each of these events occurs independently
with probability $p$, the probability that $R$ is reflexive is
$p^3$.}

\ppart[5] $R$ is symmetric.

\solution{$R$ is symmetric if:

\begin{itemize}
\item $aRb$ and $bRa$ both hold or both do not hold
\item $bRc$ and $cRb$ both hold or both do not hold
\item $aRc$ and $cRa$ both hold or both do not hold
\end{itemize}

Each of these events occurs independently with probability $p^2 + q^2$.  Therefore, all three occur with probability $(p^2 + q^2)^3$.}

\instatements{\newpage}

\ppart[3] $R$ is an equivalence relation with the equivalence classes
$\set{b}$ and $\set{a,c}$.

\solution[\vspace{3.5in}]{
$p^5q^4$.

There is only one relation, $R$, satisfying these conditions.  Of the nine
possible pairs in $\mathcal{S} \cross \mathcal{S}$, 5 must be in $R$,
namely, $(a,a),(b,b),(c,c),(a,c),(c,a)$, and the others must not be in
$R$.  
}

\ppart[5] $R$ is an equivalence relation.

\solution[\vspace{3.5in}]{
$p^9 + p^3q^6 + 3p^5q^4$.

An equivalence relation on $\mathcal{S}$, can have one, two, or three
equivalence classes.  There is only 1 relation with one class; this has
probability $p^9$.  There is 1 relation with 3 classes; this has
probability $p^3q^6$.  There are 3 relations with two classes, since there
are 3 ways to choose which element gets its own class; from the previous
part, the probability of this case is therefore $3p^5q^4$.}

\eparts

\end{examproblem}


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

\instatements{\newpage}

\begin{examproblem}{10}
You knock on the door of a home with two children.  Each child is a
boy or girl with equal probability, and each child is equally likely
to open the door.

A sample space for this experiment has outcomes that are triples whose
first element is either \texttt{B} or \texttt{G} for the sex of the elder
child, likewise for the second element and the sex of the younger child,
and whose third coordinate is \texttt{E} or \texttt{Y} indicating whether
the \emph{e}lder child or \emph{y}ounger child opened the door.  For
example, $(\mathtt{B},\mathtt{G},\mathtt{Y})$ is the outcome that the elder
child is a boy, the younger child is a girl, and the girl opened the door.

\bparts

\ppart[2] Let \emph{T} be the event that the household has two girls,
and \emph{O} be the event that a girl opened the door.  List the
outcomes in

\begin{itemize}
\item \emph{T}: \brule{5in}  \solution{GGE,GGY}
\bigskip
\item \emph{O}: \brule{5in} \solution{GGE,GGY,GBE,BGY}
\end{itemize}

\ppart[2] What is the probability $\prcond{T}{O}$, that both children
are girls, given that a girl opened the door?

\solution[\vspace{1in}]{1/2}

\instatements{\newpage}

\ppart[6] Identify exactly where the error is in the following argument.

\begin{quotation}
{\em
\noindent If a girl opens the door, then we know that there is at least
one girl in the household.  The probability that there is at least one
girl is
\begin{equation}
1 - \prob{\text{both children are boys}} = 1 - (1/2 \times 1/2) = 3/4.
\end{equation}
So,
\begin{eqnarray}
\lefteqn{\prcond{T}{\text{there is at least one girl in the household}}}\\
& = & \frac{\prob{T \intersect \text{there is at least one girl in the household}}}
{\pr{\text{there is at least one girl in the household}}}\\
& = & \frac{\prob{T}}{\pr{\text{there is at least one girl in the household}}}\\& = & (1/4) / (3/4) = 1/3.
\end{eqnarray}
Therefore, given that a girl opened the door, the probability that there
are two girls in the household is \textup{1/3}.
}
\end{quotation}

\solution{The argument is a correct proof that 
\[
\prcond{T}{\text{there is at least one girl in the household}} = 1/3.
\]
The problem is that the event, $H$, that the household has at least one girl,
namely,
\[
H \eqdef \set{\mathtt{GGE,GGY,GBE,GBY,BGE,BGY}},
\]
is not equal to the event, \emph{O}, that a girl opens the door.  These
two events differ:
\[
H-O = \set{\mathtt{BGE,GBY}},
\]
and their probabilities are different.  So the fallacy is in the final
conclusion where the value of $\prcond{T}{\text{there is at least one girl
in the household}}$ is taken to be the same as the value $\prcond{T}{O}$.
Actually, $\prcond{T}{O} = 1/2$.}

\eparts

\end{examproblem}

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

\instatements{\newpage}

\begin{examproblem}{15}  %Eric F03

Here are seven propositions:

\[
\begin{array}{rcrcr}
x_1 & \vee & x_3 & \vee & \neg x_7 \\
\neg x_5 & \vee & x_6 & \vee & x_7 \\
x_2 & \vee & \neg x_4 & \vee & x_6 \\
\neg x_4 & \vee & x_5 & \vee & \neg x_7 \\
x_3 & \vee & \neg x_5 & \vee & \neg x_8 \\
x_9 & \vee & \neg x_8 & \vee & x_2 \\
\neg x_3 & \vee & x_9 & \vee & x_4
\end{array}
\]

Note that each proposition is the OR of three expressions of the form
$x_i$ or $\neg x_i$.  Moreover, the variables in the three expressions
are different.  Suppose that we assign true/false values to the
variables $x_1, \ldots, x_9$ independently and with equal probability.
Justify your answers to the following questions.

\bparts

\ppart[3] What is the probability that the first proposition is false?

\solution[\vspace{3in}]{Each term is false with probability $1/2$.
Therefore, every term is false with probability $(1/2)^3 = 1/8$.}

\ppart[4] What is the expected number of false propositions?

\solution{Note that each proposition is false with probability $1/8$ by
the same reasoning.  Let $F_i$ be an indicator for the event that the
$i$th proposition is false.  Then the number of false propositions is
$F_1 + \ldots + F_7$ and the expected number is:

\begin{eqnarray*}
\expect{F_1 + \ldots + F_7}
    & = & \expect{F_1} + \ldots + \expect{F_7} \\
    & = & 1/8 + \ldots + 1/8 \\
    & = & 7/8
\end{eqnarray*}}


\instatements{\newpage}

\ppart[6] Use Markov's Inequality to derive a number $p > 0$ such that
all the propositions are true with probability at least $p$.

\solution[\vspace{4in}]{
Let $F$ be the number of false propositons.

\begin{eqnarray*}
\pr{\text{all true}}
    & = & \pr{F = 0} \\
    & = & 1 - \pr{F \geq 1} \\
    & \geq & 1 - \expect{F} / 1 \\
    & = & 1/8
\end{eqnarray*}
}

\ppart[2] Suppose that we generate random assignments until we find
one that makes all the propositions true.  Give an upper bound on the
expected number of assignments that we generate.  You may express your
answer in terms of the probability, $p$, from the previous part.

\solution{By the mean-time-to-success formula, the expected number of
trials is at most $1 / p = 8$.}

\eparts

\end{examproblem}


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

\instatements{\newpage}

\begin{examproblem}{15}  %Eric F03

There are 300 different episodes of the television program {\em Law
and Order}, of which 50 are {\em really great} and 250 are {\em pretty
good}.  One episode is rerun each night.  Assume that this episode is
selected uniformly at random, independent of all preceding episodes.

\bparts

\ppart[3] What is the expected number of episodes you will watch until you
see one really-great episode?

\solution[\vspace{3.5in}]{The probability of seeing a really-great
episode is $50/300 = 1/6$.  By the mean-time-to-success formula, the
expected number of episodes I must watch is 6.}

\ppart[6] Suppose that I've seen $k$ of the really-great episodes where $0
\leq k < 50$.  What is the expected number of additional episodes I must
watch in order to see a really-great episode I have not seen yet?

\solution{The probability of seeing a new really-great episode is $(50
- k)/300$.  Therefore, the expected number is $300 / (50 - k)$.}

\instatements{\newpage}


\ppart[6] What is the expected number of episodes that I must watch in
order to see {\em all} of the really-great episodes?  Your answer should
be a closed-form expression involving the $n$th Harmonic number,
\[
H_n \eqdef \frac{1}{1} + \frac{1}{2} + \ldots + \frac{1}{n}.
\]

\solution{By linearity of expectation, the answer is the expected time
to see the first really-great episode, plus the expected time to see
the second, and so forth:

\begin{eqnarray*}
\frac{300}{50} + \frac{300}{49} + \frac{300}{48} + \ldots + \frac{300}{1}
    & = & 300 H_{50}
\end{eqnarray*}
}

\eparts

\end{examproblem}

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

\iffalse

\instatements{\newpage}

\begin{examproblem}{15}   %Eric F03

There are twelve students in Nancy Plimpton's third-grade class,
including the terrifying Snivelson triplets.  There are twelve desks
in the classroom, arranged like this:

\[
\begin{array}{cccc}
\fbox{A} & \fbox{B} & \fbox{B} & \fbox{A} \\ \\
\fbox{B} & \fbox{C} & \fbox{C} & \fbox{B} \\ \\
\fbox{A} & \fbox{B} & \fbox{B} & \fbox{A}
\end{array}
\]

The teacher will select an assignment of students to desks uniformly
at random.  Two students are considered {\em next to} each other if
one is immediately left, right, behind, or in front of the other.  For
example, each student in a desk marked B is next to exactly three
other students.

Let the random variable $S$ be the number of Snivelsons that sit next
to Nancy.  Let $A$ be the event that Nancy is assigned to an $A$ desk,
$B$ be the event that she is assigned to a $B$ desk, and $C$ be the
event that she is assigned to a C desk.

\bparts

\ppart[5] What are $\pr{A}$, $\pr{B}$, and $\pr{C}$?

\solution{
}

\instatements{\newpage}

\ppart[5] What are $\expect{S \mid A}$, $\expect{S \mid B}$, and
$\expect{S \mid C}$?

\solution[\vspace{3.5in}]{
}

\ppart[5] What is the expected number of Snivelsons that will sit next
to Nancy?

\solution{
}

\eparts

\end{examproblem}
\fi


\iffalse

\instatements{\newpage}


\begin{examproblem}{15}   %Eric F03

Stinky Peterson is taking 7.393 ({\em The Evolution of Nasty, Crawly
Things}).  The final exam is structured as follows:

\begin{itemize}

\item The professor distributes a list of 12 questions two weeks
before the exam, so that students can prepare answers in advance.

\item The professor selects 4 of these questions uniformly at random
and puts them on the final exam.

\item Each student must answer 2 of the questions on the exam.

\end{itemize}

Stinky notes that each possible outcome of the exam-creation process
corresponds to a 12-bit sequence $(b_1, b_2, \ldots, b_{12})$ that has
exactly 4 ones.  In particular, $b_i = 1$ if the $i$th question is on
the exam and $b_i = 0$ if the $i$th question is not on the exam.

\bparts

\ppart[3] How many different final exams are possible?

\solution[\vspace{3in}]{This is the number of 12-bit sequences with
exactly 4 ones, which is $\binom{12}{4}$.}

\instatements{\newpage}

\ppart[3] Stinky has time to prepare answers to only the first 5
questions in advance.  Let $E$ be the event that the final contains
{\em exactly} 2 of the questions Stinky prepared.  Describe all
outcomes in the event $E$ in terms of bit sequences.

\solution[\vspace{3.5in}]{The event $E$ contains all 12-bit sequences
with exactly 2 ones in the first 5 positions.}

\ppart[3] What is $\pr{E}$?

\solution{The number of outcomes in $E$ is $\binom{5}{2} \cdot
\binom{7}{2}$ since we must put 2 ones in the first 5 positions and 2
ones in the last 7 positions.  Since all outcomes are equally likely,
we have:

\begin{eqnarray*}
\pr{E} & = & \frac{\binom{5}{2} \cdot \binom{7}{2}}{\binom{12}{4}}
\end{eqnarray*}
}

\instatements{\newpage}

\ppart[3] Let $F$ be the event that the final contains {\em at least}
2 of the questions Stinky prepared.  Describe all outcomes in event
$F$.

\solution[\vspace{3.5in}]{The event $F$ contains all sequences with 2,
3, or 4 ones in the first 7 positions.}

\ppart[3] What is $\pr{F}$?

\solution{
Reasoning as before, we get:

\begin{eqnarray*}
\pr{F} & = &
\frac{
\binom{5}{2} \cdot \binom{7}{2} +
\binom{5}{3} \cdot \binom{7}{1} +
\binom{5}{4} \cdot \binom{7}{0}}{\binom{12}{4}}
\end{eqnarray*}
}

\eparts

\end{examproblem}
\fi

\instatements{\newpage}

\begin{examproblem}{15}  %S02 Final

Suppose successive digits from zero to nine are generated independently
until the four digit sequence \textbf{9999} appears.  What is the expected
number of digits generated?  Briefly explain your answer.

\hint Parse the sequence into consecutive ``tries to get 9999'', where
a ``try'' is either a single digit other than 9, or a 9 followed by a
single digit other than 9, etc.  For example, the sequence
92349982999769999 parses into eight tries:
\[
/92/3/4/998/2/9997/6/9999/.
\]

\solution{11110.

By Wald's Theorem, the expected number is the mean time to a
successful try, namely $10^4$, times the expected length of a try.
Notice that a try is of length four iff it begins with three nines, so
the probability of a length four try is $1/10^3$.  That means the
expected length of a try is
\[
1 \cdot \frac{9}{10} + 2 \cdot \frac{1}{10}\frac{9}{10} + 3 \cdot
(\frac{1}{10})^2\frac{9}{10} + 4 \cdot (\frac{1}{10})^3
 =  (900 + 180 + 27 + 4)/1000 = 1111/1000
\]
Thus on average, we will have to read 11110 digits in order to see
``9999''.}

\end{examproblem}



\instatements{\newpage}

\begin{examproblem}{10}  %S02 Final

Let $G_1, G_2, G_3, \dots, $ be an infinite sequence of independent random
variables with the same distribution and the same expectation, $\mu$, and
let
\[
f(n, \epsilon) \eqdef \pr{\abs{\frac{\sum_{i=1}^n G_i}{n} - \mu} \leq \epsilon}.
\]
The Weak Law of Large Numbers can be expressed as a logical formula of
the form:
\[
\forall \epsilon > 0\,Q_1\,Q_2\dots\, [f(n,\epsilon) \geq 1 - \delta]
\]
where $Q_1Q_2\dots$ is a sequence of quantifiers from among:
\begin{itemize}
\item $\forall n_0$
\item $\forall n \geq n_0$
\item $\forall \delta > 0$
\item $\forall \delta \geq 0$
\item $\exists n_0$
\item $\exists n \geq n_0$
\item $\exists \delta \geq 0$
\item $\exists \delta >0$
\end{itemize}
Here the $n$ and $n_0$ range over natural numbers, and $\delta$ and
$\epsilon$ range over real numbers.

Write out the proper sequence $Q_1Q_2\dots$ \brule{3in}

\solution{$\forall \epsilon > 0 \, \forall \delta > 0\, \exists n_0\,
\forall n \geq n_0$}

\end{examproblem}


\instatements{\newpage}

\begin{examproblem}{20}

Let $T_n$ be the graph consisting of $n$ consecutive triangles arranged as
follows:
\begin{verbatim}
                 __________________________ ..._ ________
                /\      /\      /\      /        \      /
               /  \    /  \    /  \    /   ...    \    /
              /    \  /    \  /    \  /            \  /
             /______\/______\/______\/___ ... ______\/

\end{verbatim}

\bparts

\ppart[4] Each edge in $T_n$ is colored red with probability $r$ and blue
with probability $b \eqdef 1 - r$ mutually independently.  A triangle is
{\em monochromatic} if its edges are all blue or all red.  What is the
probability, $m$, that a particular triangle is monochromatic?

\solution[\vspace{2.5in}]{The triangle is all red with probability $r^3$
and all blue with probability $b^3$, and so it is monochromatic with
probability $m = r^3 + b^3$.}

\ppart[3] Let $I_T$ be an indicator random variable for the event that a
given triangle, $T$, is monochromatic.\\
What is $\expect{I_T}$? \brule{0.5in}
What is $\variance{I_T}$?  \brule{0.5in}\\

You may state your answer in terms of the probability, $m$, from the
previous problem part.

\solution[\vspace{3.5in}]{
\begin{align*}
\expect{I_T} = & \pr{I_T = 1} = m & \text{since $I_T$ is 0-1 valued.}\\
\variance{I_T} = & \expect{I_T^2} - \expect{I_T}^2 \\
               = & m - m^2.
\end{align*}
}

\ppart[4] Let $T$ and $T'$ be any two different triangles, and suppose
that $r = 1/2$.  Show that the random variables $I_T$ and $I_{T'}$ are
independent.

\solution[\vspace{3.5in}]{
It is enough to show that
\begin{eqnarray*}
\pr{I_T = 1 \cap I_{T'} = 1} & = & \pr{I_T = 1} \cdot \pr{I_{T'} = 1}.
\end{eqnarray*}

The probability on the left is the probability that all five edges in $T
\union T'$ are the same color, namely, $r^5 + b^5 = 1/16$, and the
probability on the right is $(r^3 + b^3)^2 = 1/16$.}

\iffalse

\ppart[3] For each triangle in the graph, we can consider the
event that the triangle is monochromatic.  Are all such
events mutually independent when $r = 1/2$?  Justify your answer.

\solution[\vspace{3.5in}]{Yes.}
\fi


\ppart[4] Let $M$ be the random variable equal to the total number of
monochromatic triangles in the graph.  If $r = 1/2$, what is
$\variance{M}$?

\solution[\vspace{3in}]{$3n/16$.

This follows because in this case $m = r^3+b^3 = 1/4$, and
\begin{eqnarray*}
M & = & I_{T_1} + I_{T_2} + \ldots + I_{T_n},
\end{eqnarray*}
and since the indicator random variables are pairwise independent, we have:
\begin{eqnarray*}
\variance{M} & = & \variance{I_{T_1}} +
                   \variance{I_{T_2}} + \ldots +
                   \variance{I_{T_n}} \\
             & = & n\variance{T_1}\\
             &=  & n(m-m^2)= n(3/16).
\end{eqnarray*}
}

\instatements{\newpage}

\ppart[5] Prove that
\[
\lim_{n\to\infty} \pr{\abs{M - \expect{M}} \geq n/1000} = 0.
\]

\solution[\vspace{3.5in}]{
\begin{align*}
\pr{\abs{M - \expect{M}} \geq n/1000} & \leq  \variance{M}/(n/1000)^2
           & \text{by Chebyshev}\\
       & = (3n/16)10^6/n^2\\
       & = 3\cdot 10^6/16n\\
       & \to \infty  & as n \to \infty.
\end{align*}
}

\eparts

\end{examproblem}

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

\instatements{\newpage}

%source: fall99 final exam problem 8
%topic: Markov Theorem

\begin{examproblem}{15}
A herd of cows is stricken by an outbreak of \emph{cold cow disease}.  The
disease lowers the normal body temperature of a cow, and a cow will die if
its temperature goes below 90 degrees F.  The disease epidemic is so
intense that it lowered the average temperature of the herd to $85$
degrees.  Body temperatures as low as $70$ degrees, \textbf{but no lower},
were actually found in the herd.

\bparts

\ppart[10] Based solely on the information above, state a \textbf{largest
possible} lower bound on the probability that a randomly chosen cow from
herd will have a temperature too low to survive.

\solution[\vspace{3in}]{
Let $T$ be the temperature of a random cow.  Apply Markov's Bound to
$T-70$:
\[
\prob{T \geq 90} = \prob{T-70 \geq 20} \leq \expect{T-70}/20 = (85-70)/20 = 3/4,
\]
so
\[
\pr{T < 90} \geq \frac{1}{4}.
\]
}

%\vspace{3in}

\ppart[5] Suppose there are 400 cows in the herd.  Give an example set of
temperatures for the cows so that the probability that a randomly chosen
cow will have a fatal temperature is as small as possible.

\solution[\vspace{4cm}]{
Let 100 cows have 70 degrees and 300 have 90
degrees.  The mean is
\[
(1/4)70 + (3/4)90 = 85,
\]
as required.
}

%\vspace{2in}

\eparts

\end{examproblem}

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

\instatements{\newpage}

\begin{examproblem}{10}
In the class Notes, we analyzed the Gambler's Ruin game where the
Gambler's initial stake was \$$n$, and he made independent bets with
probability $p$ of winning \$1 and probability $q \eqdef 1-p$ of losing
\$1, until his stake was reduced to zero or he reached his goal of \$T.
We let $w_n$ be the probability that the Gambler \emph{wins} by reaching
his goal before running out of money.  The problem of finding a formula
for $w_n$ was reduced to solving the following quadratic equation in $c$:
\[
c^2 - \frac{c}{p} + \frac{q}{p} = 0.
\]

Now we consider a slight alteration of the game: the probability of
winning each bet is still $p$, but instead of winning \$1 on a winning
bet, the Gambler wins \$2.  He still loses only \$1 on a losing bet.
Finding a formula for $w_n$ in this case reduces to solving a cubic
equation in $c$:
\[
a_3c^3 + a_2c^2 + a_1c + a_0 = 0.
\]
Fill in values for the coefficients of this cubic formula:
\begin{align*}
a_3 &\brule{1cm},\\
a_2 &\brule{1cm},\\
a_1 &\brule{1cm},\\
a_0 &\brule{1cm}.
\end{align*}
A correct answer gets full credit, but you can get partial credit only if
you include an explanation with your answer.

\solution[\vspace*{3in}]{
In this case we have
\[
w_n = pw_{n+2} + qw_{n-1},
\]
so assuming $w_n = c^n$ for some $c$, we have
\[
c^n = pc^{n+2} + qc^{n-1},
\]
and hence
\[
pc^{n+2} - c^n + qc^{n-1} = 0.
\]
Factoring out $c^{n-1}$ yields the desired cubic formula
\[
pc^3-c+q.
\]
That is
\begin{align*}
a_3 = & p,\\
a_2 = & 0,\\
a_1 = & -1,\\
a_0 = & q.
\end{align*}
}
\end{examproblem}

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

\end{document}
