\documentstyle[12pt]{article}
\input{/a/class/6.042/spring94/handouts/macros-course}
%\newcommand\npage{\vspace{.8in}}
\newcommand\npage{\newpage}

%%	Three typos fixed after the test:  
%%		(was):	quiz ``contains 12 problems''
%%		(was):	``You may use one ``...[crib sheet]
%%		Problem 4:  let the second set be S' since it's not S.
%%				-SJP, 4/22.

\setcounter{page}{0}

\begin{document}

%\handout{practice-quiz-2}{Practice Quiz 2}{April 15, 1994}
\examinitials{Quiz 2}{April 20, 1994}


\begin{closeitemize}

\item This quiz ends at 9 {\sc p.m.} It contains 8 problems.  You
have 120 minutes to earn 105 points.

\item {\bf Initial the top of each page of your quiz. This is worth
5 points.}

\item This quiz is closed book.  You may use two $8\frac{1}{2}''\times
11''$ handwritten crib sheets. No calculators or electronic playback
devices are permitted.

\item Write your solutions in the space provided.  If you need more
space, write on the back of the sheet containing the problem.  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.  You will be
graded not only on the correctness of your answer, but also on the
{\bf clarity} with which you express it.  {\bf Be neat.}

\end{closeitemize}



\renewcommand{\arraystretch}{.5}
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
& &\hspace*{1in}\\
Problem&Points&Grade\\
& &\\
\hline
\hline
& &\\
Initials & 5 & \\
& &\\
\hline
& &\\
1 & 10 & \\
& &\\
\hline
& &\\
2 & 10 & \\
& &\\
\hline
& &\\
3 & 14 & \\
& &\\
\hline
& &\\
4 & 16 & \\
& &\\
\hline
& &\\
5 & 16 & \\
& &\\
\hline
& &\\
6 & 10 & \\
& &\\
\hline
& &\\
7 & 10 & \\
& &\\
\hline
& &\\
8 & 14 & \\
& &\\
\hline
\hline
& &\\
Total & 105 & \\
& &\\
\hline
\end{tabular}
\end{center}
\renewcommand{\arraystretch}{1}

\bigskip
\bigskip

\noindent Name:\ \mbox{}\hrulefill\mbox{}\par

\newpage


\begin{problems}

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


%\npage%5
%\problem \points{10} How many orderings exist for a standard card
%deck of $52$ cards if all the cards of the same suit are adjacent?
%
%You may leave your answer in terms of factorials and powers.
%

\npage%6
\problem \points{10} In how many ways can 6 men and 6 women be seated
at a round table if men and women must sit in alternate seats? Since
the table is round, rotating their positions does not count as a new
seating arrangement. 


You need not simplify your answer---you may
leave it in terms of factorials, powers, etc.

%You may leave your answer in terms of factorials and powers.

\npage%7
\problem \points{10} 

\begin{problemparts}

\problempart
What is the number of ways to distribute $n$ 
distinct toys among $k$ distinct children.  
There are no constraints on the number of presents a child can receive.

\vspace{3in}

\problempart How many ways could the toys be distributed if the
toys were indistinguishable?



\end{problemparts}



\npage%8
\problem \points{14} 

\begin{problemparts}

\problempart
Use a combinatorial argument to prove that
\[ \sum_{k=0}^n {r\choose k} {s \choose n-k} = {r+s\choose n} \]
for all natural numbers $r,s,n$.
\vspace{2.5in}

\problempart
Prove the same thing using the binomial theorem and the identity
\[(1+x)^r (1+x)^s = (1+x)^{r+s}\quad.\]

\end{problemparts}

\npage%9
\problem \points{16} 
\begin{problemparts}
\problempart
What is the number of 11-combinations of the multiset 
\mbox{$S = \{\infty\cdot a, \; \infty\cdot b, \; \infty\cdot c, \; \infty\cdot d\}$?}

(You need not simplify your answer---%
you may leave it in terms of factorials, powers, etc.)

\vspace{3in}

\problempart
Use inclusion-exclusion to 
determine the number of 11-combinations of the
multiset $S' = \{\infty\cdot a, \; 4\cdot b, \; 5\cdot c, \; 7\cdot d\}$.

(You need not simplify your answer---%
you may leave it in terms of factorials, powers, etc.)

\end{problemparts}

\npage%10
\problem \points{16} Let $a_n$ be the number of $n$-digit numbers composed
of the digits $1,2,$ and $3$ such that the number of $1$'s is odd and
the number of $2$'s is even. 

\begin{problemparts}

\problempart
Find the exponential generating function for
the sequence $\langle a_0,a_1,a_2,\ldots\rangle$.
\vspace{3.5in}

\problempart  Find a simple formula for $a_n$.

\end{problemparts}


\npage%1
\problem \points{10}
Suppose you are playing a game that results in either a win
or a loss.  
The outcomes of the games are mutually independent and you win 
each game with probability $2/3$.
Suppose you play 7 times. What is the probability that you win 
exactly 3 out of the last 4 games?

Describe the sample space and show your calculations.

\npage%2
\problem \points{10}
In a certain village, 20\% of the population has contracted disease $D$. 
When a person who has the disease is tested for it, 
he or she tests positive with probability~$9/10$. 
A person without $D$ tests positive for it with probability~$3/10$. 
If a villager is chosen uniformly at random and tests positive for $D$, 
what is the probability that he or she actually has the disease?

(This is not a trick question---the probability is not 0 or 1.)\\
Describe the sample space and show your calculations.

%\npage%3
%\problem \points{10}
%Consider the following version of the Monty Hall game.
%You are shown three doors. There is a prize behind
%{\em two} of the doors, and a goat behind the other.
%As usual, you pick a door. Now however Monty reveals 
%another door that has a prize behind it. He then offers you
%the opportunity either to stick with what's behind the first
%door you chose, or to switch and take what's behind the other
%unopened door. 
%
%Assume that Monty picks the doors for his prizes (and the
%door he opens) at random.
%What is the probability of winning if you play the switch
%strategy. What is your probability of winning if you don't
%switch. Show any necessary calculations.
%

\npage%4
\problem \points{14}
Consider the experiment of tossing three fair coins. 
The probability for each  coin to come 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 the first coin comes up heads.

Let $A_2$ be the event that the first two coins come up the same
(that is, they are either both heads or both tails).

Let $A_3$ be the event that more coins come up heads than tails.

Let $A_4$ be the event that the last coin is tails.

\begin{problemparts}

\problempart
What is the sample space?
\vspace{1.8in}

\problempart
What is the probability of each sample point?
\vspace{1.8in}

\problempart
Calculate $\rm{Prob}[A_4 \mid A_2 \land A_3]$.
\vspace{1.8in}

\problempart %\points{}
Are $A_1$ and $A_2$ independent? Justify your answer.
\vspace{2.3in}

\problempart
Are $A_3$ and $A_4$ independent? Justify your answer.
\vspace{2.3in}

\problempart %\points{}
Find 3 events (from $A_1,\ldots,A_4$)  that are mutually 
independent. Justify your answer.

\end{problemparts}



% \npage%11
% \problem \points{10} Use generating functions to solve the recurrence
% \[ a_n=\left\{  
% \begin{array}{ll}
%                 0&\mbox{if $n=0$} \\
%                 3&\mbox{if $n=1$} \\
%                 a_{n-1} + 2a_{n-2}&\hbox{for $n\ge2$}. \\
% \end{array} \right. \]
% For partial credit, just find a simple expression for an ordinary generating
% function for the sequence $\langle a_0,a_1,a_2,\ldots\rangle$.
% 
% \npage%12
% \problem \points{10} Use the pigeonhole principle to prove that if 
% $m$ and $n$ are two positive integers then there exist distinct
% natural numbers $i$ and $j$ such that $m^i-m^j$ is divisible by
% $n$.
% 
 
 
 \end{problems}
 
 \end{document}
 
