\documentstyle[12pt,macpsfig,amssymb]{article}
\input{/a/class/6.042/fall94/handouts/macros-course}

%	\addtolength{\topmargin}{-.2in}
%	\setlength{\textheight}{9in}

\setcounter{page}{0}

\renewcommand{\bar}{\overline}

%\newcommand{\pr}{\problem}
\newcommand{\pr}{\newpage\problem}
%\renewcommand{\bparts}{\begin{testproblemparts}}
%\renewcommand{\eparts}{\end{testproblemparts}}

\begin{document}

\examinitials{Quiz 2}{November 29, 1994}


\begin{closeitemize}

\item Put your name on the top of each page---the pages of this booklet  
will be separated for grading.

\item This quiz ends at 9 {\sc p.m.} It contains seven problems on
pages numbered 1 through~9.  You have 120 minutes to earn 100 points.

\item This quiz is closed book.  You may use one $8\frac{1}{2}''\times
11''$ handwritten crib sheet.  You may not use a calculator.

\item Write your solutions in the space provided.  If you need more
space, write on the back of the sheet containing the problem.  Please do not
put part of the answer to one problem on the back of the sheet for
another problem.

\item Do not spend too much time on any problem.  Read them all
through first and attack them in the order that allows you to make the
most progress.

\item Show your work, as partial credit will be given.  Explain your
answers.  You will be graded not only on the correctness of your
answer, but also on the clarity with which you explain it.  Be neat.

\end{closeitemize}

\renewcommand{\arraystretch}{.5}
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
& &\hspace*{1in}\\
Problem&Points&Grade\\
& &\\
\hline
\hline
& &\\
1 & 10 & \\ & &\\ \hline	& &\\
2 & 10 & \\& &\\\hline& &\\
3 & 30 & \\& &\\\hline& &\\
4 & 10 & \\& &\\\hline& &\\
5 & 20 & \\& &\\\hline& &\\
6 & 10 & \\& &\\\hline& &\\
7 & 10 & \\& &\\
\hline
\hline
& &\\
Total & 100 & \\
& &\\
\hline
\end{tabular}
\end{center}
\renewcommand{\arraystretch}{1}
\bigskip
\bigskip
\bigskip

\noindent Name:\ \mbox{}\hrulefill\mbox{}\par
\bigskip \bigskip
\noindent Please circle your TA's name: 
 \hspace{.5in} Andrew 
 \hspace{.5in} David
 \hspace{.5in} Keith
 \hspace{.5in} Victor

\newpage
\begin{problems}


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

\pr 
\points{10} 

Use induction to prove that the recurrence 
\[T(n) = 4T(\floor{n/2}) + n^2\ ,\]
where $T(1)= 0$ has solution
\[T(n) = O(n^2\lg n).\]


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

\pr 
\points{10} 

Suppose that $a_0=0$ and $a_1=2$, and that $a_n$ obeys the
recurrence
\[
a_n = 4a_{n-1}  - 4a_{n-2}\ 
\]
for $n\geq 2$.  Use the characteristic equation method or another
solution technique to find a closed-form expression for~$a_n$.

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

\pr
\points{30} 

For each of the following problems, determine the value or expression
requested.  Briefly justify your answers.

\bparts

\ppart How many of the billion numbers in the range from 1 to
1,000,000,000 contain the digit~$1$?  You need not simplify your
answer.  (\hint Don't do inclusion/exclusion.)

\vspace*{3.5in}

\ppart How many integers in the range 1 to 60,000 are divisible by at
least one of the numbers 4, 5, or~6?  Show your derivation, and give a
numerical value for your answer.

\newpage

\ppart Consider the set of $10^n$ $n$-digit integers (where leading
0's are permitted).  Consider two integers to be equivalent if the
digits of one are a permutation of the digits of the other.  How many
equivalence classes of the $10^n$ $n$-digit integers are there?  You
need not simplify your answer.

\vspace*{3.5in}

\ppart How many ways are there to order the 26 letters of the alphabet
so that no two of the vowels {\tt a}, {\tt e}, {\tt i}, {\tt o}, {\tt
u} appear consecutively?  You need not simplify your answer.

\eparts



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

\pr 
\points{10} 

Toscanini's offers bowls of ice cream containing scoops chosen from
the flavors chocolate, strawberry, vanilla, and coffee.  Use
generating functions to compute the number of distinct bowls of ice
cream with $n$ scoops such that there are an even number of chocolate
scoops, a number of strawberry scoops that is a multiple of 4, at most
3 vanilla scoops, and 1 or 2 coffee scoops.


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


\pr 
\points{20} 

Consider the experiment of tossing three fair coins.  The probability
that each coin comes up heads is $1/2$, and the results of the three
flips are mutually independent.  (For this problem you can use either
definition of mutual independence that was given in class.)

Let $A_1$ be the event that Coin 1 comes up heads.

Let $A_2$ be the event that Coins 1 and 2 come up different.

Let $A_3$ be the event that Coins 2 and 3 come up the same.

Let $A_4$ be the event that Coins 1 and 3 come up different.

Let random variable $R$ be the number of heads shown by Coins 1 and 2
minus the number of heads shown by Coin~3, and let $A_5$ be the event
that $R>0$.

\bparts

\ppart Draw or describe the sample space.  What is the probability of
each sample point?

\vspace{2.5in}

\ppart
Calculate $\prob{A_5}$.  Show your work.

\vspace{1.5in}

\ppart

Calculate $\prob{A_4\mid A_1 \wedge A_2 \wedge A_3}$?  Show your work.

\eparts
\newpage

Which of the following sets of events are mutually independent?
Briefly justify your answers.

\bparts

\ppart  $A_1$ and $A_2$.

\vspace{2in}

\ppart  $A_2$ and $A_3$.

\vspace{2in}

\ppart  $A_1$, $A_2$, and $A_3$.

\vspace{2in}

\ppart  $A_2$, $A_3$, and $A_4$.


\eparts


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

\pr 
\points{10} 
\bparts
\ppart
Prove that if events $A$ and $B$ are independent, then
events $\bar A$ and $\bar B$ are independent.

\vspace{2.5in}

\ppart Is it always true that $\prob{A\mid B} = \prob{B\mid A}$ if $A$
and $B$ are independent?  Justify your answer.

\vspace{2.5in}

\ppart Is it always true that $\prob{A\vee B} = \prob{A}+\prob{B}$ if
$A$ and $B$ are independent?  Justify your answer.

\eparts

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

\pr 
\points{10} 

It was recently reported in {\it Technology Review\/} that scientists
at MIT have discovered that lycanthropy (the disease that makes one a
werewolf) is an inherited disease passed by a recessive gene from
parents to their offspring.  They have discovered that each person has
a pair of genes drawn from the set $\set{{\tt d}, {\tt D}}$ that
determine whether that person is a werewolf as follows:

\begin{tabular}{ll}
$\ang{{\tt d}, {\tt d}}$ &  Is a werewolf.\\
$\ang{{\tt D}, {\tt d}}$ &  Is not a werewolf, but is a carrier.\\
$\ang{{\tt d}, {\tt D}}$ &  Is not a werewolf, but is a carrier.\\
$\ang{{\tt D}, {\tt D}}$ &  Is not a werewolf or a carrier.
\end{tabular}

A child inherits two genes, one from each of his or her parents, where
each gene is chosen uniformly and independently.  Before a person
turns age 20, it is impossible to tell whether he or she is a
werewolf.  If a person is a werewolf, however, he or she exhibits the
classical symptoms during the first full moon after his or her 20th
birthday.

Alice and Bob are a 60-year-old married couple who are not werewolves.
They have three children---Carol, age 38; Dan, age 27; and Edith,
age~18.  Carol is not a werewolf, Dan is a werewolf, and since Edith
is not yet 20, we do not yet know whether she is a werewolf.

\bparts

\ppart What is the probability that Edith is a werewolf?

\vspace{1in}

\ppart What is the probability that Carol is a carrier?

\vspace{1in}

\ppart You learn that Carol is married to a werewolf and that they
have a child who is not a werewolf.  Given this new information, what
is the probability that Carol is a carrier?

\eparts

\end{problems}

\end{document}


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

\remove{
\pr 
\points{???} 
OJ's blood test reveals that his blood is (1) type O, (2) rH negative, 
and (3) thick.  
Tests of blood from the scene of the crime reveal the same data.
It is known that one-tenth of the general population has blood type O,
one-third is rH negative, and one-fifth has thick blood.
\bparts
\ppart
At the trial, a lab technician from Bobo's Blood Lab is called to testify.
He claims that the probability a random person matches this data is~$1/150$.\\
Is he correct?
What can you say about the probability that a random person matches this data?
\ppart
On re-examination, it is found that rH-factor and blood thickness are
independent.  What can you say now 
about the probability that a random person matches this data?
\ppart
Still later, it is revealed that all pairs of blood data are independent.
What can you say now 
about the probability that a random person matches this data?

\eparts

}

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

\remove{
\pr 
\points{???} 
Give asymptotic ($\Theta$) bounds for the following recurrences.
For each, $T(1)=1$, and you may assume $n$ is a power of $4$ or $2$
as necessary, so the argument to $T$ is always an integer.
\bparts
\ppart  $T(n) = 4T(n/4) + n$
\ppart  $T(n) = 3T(n/2) + n$
\ppart  $T(n) = 4T(n/2) + n^2$
\eparts
}





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

\remove{
\pr 
\points{???} 

Let $h(k)$ be the number of $n$-bit binary strings such that neither 0
nor 1 appears exactly twice. 
\bparts

\ppart Find the generating function $H(x)$ for the sequence
$\ang{h_n}$.

\ppart Find a concise formula for $h_n$.  (For partial credit, solve
the problem for $n \geq 5$.)

\eparts
}

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

\remove{
\pr 
\points{???} 

Determine the generating function $A(x)$ for the sequence determined by
the following recurrence:
\[a_n = \cases{1 & \cif{n<2\ ,}\\
	       2a_{n-1}+3a_{n-2} +4 & \cif{n\geq 2\ .}}
}

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

\remove{
\pr
\points{???}
Give a succinct formula for the coefficient $a_n$ of $x^n$ in the
following formula:
\[ A(x) = \frac{3x}{2-x-x^2}\ .\]
}

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

\remove{
\pr 
\points{???} 
The lottery game Keno is actually played with the lottery randomly 
choosing a subset of 20 numbers from $\set{1,\dots, 80}$
(uniformly from among all such subsets)
and the player choosing a subset of size between 1 and~12.
.....
}

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

\remove{

\pr 
\points{???} 

In poker, 5-card stud is often played with ``deuces wild'', so that a
2 may assume any value a player likes.  Determine whether a
5-of-a-kind is less or more likely than a royal flush when the hands
are drawn at random from a standard 52-card deck.  (A 5-of-a-kind is
the hand when all cards have the same value, ace through king.  A
royal flush is the hand ace-king-queen-jack-10, all of the same suit.
When deuces are wild, deuces can substitute for any of these cards.)
Explain your answer.

}

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