\documentstyle[12pt]{article}
\input{macros-course}
%\newcommand\npage{\vspace{.8in}}
\newcommand\npage{\newpage}

\setcounter{page}{0}

\begin{document}

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


\begin{closeitemize}
\item Solutions to this practice quiz will be available in the 
regular 6.042 drawer outside NE43-201 on Tuesday, April 19. 

\item This quiz contains 12 problems. 
 You have 120 minutes to earn 125 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
clarity with which you express it.  Be neat.

\end{closeitemize}
\bigskip
\vspace{3in}
\bigskip

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

\newpage
\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 & 10 & \\
& &\\
\hline
& &\\
4 & 10 & \\
& &\\
\hline
& &\\
5 & 10 & \\
& &\\
\hline
& &\\
6 & 10 & \\
& &\\
\hline
& &\\
7 & 10 & \\
& &\\
\hline
& &\\
8 & 10 & \\
& &\\
\hline
& &\\
9 & 10 & \\
& &\\
\hline
& &\\
10 & 10 & \\
& &\\
\hline
& &\\
11 & 10 & \\
& &\\
\hline
& &\\
12 & 10 & \\
& &\\
\hline
\hline
& &\\
Total & 125 & \\
& &\\
\hline
\end{tabular}
\end{center}
\renewcommand{\arraystretch}{1}
\newpage

\begin{problems}

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


\npage
\problem \points{10}
Suppose you are playing a game that results in either a win
or a loss.  If you play 4 times, 
what is the probability that you will win exactly three times?
Assume that the
outcomes of the games are mutually independent and that you win a game with
probability $1/3$.

Describe the sample space and show your calculations.

\npage
\problem \points{10}
Suppose you are shown two  fair coins and a two-headed coin.
They are then separated and hidden from you and you're 
allowed to pick one coin at random. Once you've picked
the coin, it is flipped twice for you and you're allowed
to view the results. Supposing that the coin turns up
heads both times, what is the probability that it's the
fair coin?
Assume you can't cheat,
that is you have probability $2/3$ of picking a fair coin,
and that the tosses of a fair coin are independent.

Describe the sample space and show your calculations.

\npage
\problem \points{10}
Consider the following version of the Monty Haul game.
The game is played normally, with one prize and three
doors and Monty picks the box for the prize randomly.
In this game however, Monty always opens the lowest numbered
box not containing a prize.
Analyze the following two strategies.

Strategy A: You always pick box 1.
When Monty offers you the choice to switch you always
accept it.

Strategy B: You always pick box 1.
You switch only if Monty reveals box 3.

\begin{problemparts}

\problempart
What is the probability of winning for each strategy
assuming Monty reveals box 3?

\problempart
What is the probability of winning for each strategy
assuming Monty reveals box 2?

\problempart
What is the overall probability of winning for each strategy?

\end{problemparts}



\npage
\problem \points{10}
Consider the following experiment. You roll a fair six sided
die three times. Assume that the three rolls are mutually independent.

Let $A_1$ be the event that the first roll comes up 1.

Let $A_2$ be the event that the sum of the first two rolls
is even.

Let $A_3$ be the event that the second roll is divisible by 3.

Let $A_4$ be the event that sum of all three rolls is at most 4.

Let $A_5$ be the event that the last roll comes up 1.

\begin{problemparts}

\problempart
What is the sample space?

\problempart
What are the probabilities of each atomic event?

\problempart %\points{}
Are $A_2$ and $A_4$ independent?

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

\problempart %\points{}
Is any event (again, one of $A_1,\ldots,A_5$)  
not independent of all the other events? (Prove your answer.)



\end{problemparts}

\npage
\problem \points{10} How many orderings exist for a standard card
deck of $52$ cards if all of the spades must appear in order but
not necessarilly in a single block?

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

\npage
\problem \points{10} In how many ways can 12 people
be seated at a square table, 3 on each side?
Since the table is square, rotating their positions so that
the people on the corners stay on the corners does not 
count as a new seating arrangement. 

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

\npage
\problem \points{10} 
Let $n$ and $k$ be positive integers.
What is the number of ways to distribute $n$ 
distinct toys among $k$ distinct children such that each child
has at most 1 toy?

\npage
\problem \points{10} Use a combinatorial argument to prove that
\[ \sum_{k=0}^n {n\choose k}^2 = {2n\choose n} \]
for any natural number $n$.

Hint: ${n\choose k}^2={n \choose k}{n \choose n-k}$.

\npage
\problem \points{10} Use inclusion-exclusion to 
determine the number of 10-permutations of the
multiset $\{4\cdot a, 4\cdot b, 4\cdot c, \infty\cdot d\}$.

You may leave your answer in the form of a sum or difference of
powers and binomial coefficients.

\npage
\problem \points{10} Let $a_n$ be the number of $n$-element
multisets composed
of the letters a, b, and c such that the number of a's is even,
the number of b's is odd, and the number of c's is odd. 

\begin{problemparts}

\problempart
Find the ordinary generating function for
the sequence $\langle a_0,a_1,a_2,\ldots\rangle$.

\problempart  Find a relatively simple formula for $a_n$.

\end{problemparts}

\npage
\problem \points{10} Use generating functions to solve the recurrence
\[ a_n=\left\{  
\begin{array}{ll}
                1&\mbox{if $n=0$} \\
                3&\mbox{if $n=1$} \\
                a_{n-1} + a_{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
\problem \points{10} Use the pigeonhole principle to argue that the
decimal expansion of a rational number $m/n$ is repeating.
For example, $26199/99900 = .26145145145145\ldots$
State explicitly what are the pigeons and what are the holes.

(Hint: use the grade-school method of long division.)


\end{problems}

\end{document}
