\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


\def\brule#1{\instatements{\enskip\vrule width#1 height -1.1pt depth 1.5pt\relax}}

\instatements{
\renewcommand{\exampreamble}{	% !! renew \exampreamble 
  \textbf{Circle the name of your Tutorial Instructor}:
  \begin{center}
  \renewcommand{\arraystretch}{1.5}
  \begin{tabular}{llllllll}
  Adrian & Georgi & Josh  & Karen & Lee & Min  & Nikos & Tina   
  \end{tabular}
  \end{center}
  \begin{itemize}
  \item 
  This quiz is \textbf{closed book}. There is an \textbf{Appendix} 
  with standard definitions.
  \item 
  There are five (5) problems totaling 100 points. Total time is 120 minutes. 
  %% Problems are labeled with their point values.
  \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
  lecture notes.
  \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} 
\quiz{2}
%\quiz{2}			% !! start the paper

\iffalse

{\bf TOPICS:
\begin{enumerate}
 \item COMMENT OUT IN FINAL VERSION!!!!!
 \item Series (Arithmetic, Geometric, Harmonic)
 \item Annuities
 \item Orders of Growth, Stirlings Formula
 \item Counting: Sum rule, Product Rule, Trees, Pigeonhole
 \item Counting: Permutations, r-Permutations
 \item Counting: Combinations, Binomial Theorem, Combinatorial arguments
 \item Counting with Repetition: Multinomial Coefficients, Stars n Bars
 \item Probability: Probability space, Trees, Conditional probability
\end{enumerate}
}
\fi

%% NEWPAGE--------------------------------------------------
\instatements{\newpage}

\begin{examproblem}{15}
Chuck Vest is planning to set aside \$100M of MIT endowment funds in the
year 2002 for student scholarships.  His plan is to offer the same annual
amount for student scholarships, starting as soon as the money is
available in 2002 and continuing through 2102, at which point the \$100M
will be exhausted.

\bparts

\ppart[6]
Assuming Chuck can count on earning a 3\% annual return on the funds he
sets aside, how much scholarship money can he offer each year?  Let
$r\eqdef 1/1.03$, and find a closed form formula in terms of $r$ for the
annual number of dollars; you do not have to evaluate the formula.  (Full
credit for a formula that evaluates to the right answer.  Partial credit
for an incorrect formula will only be considered when it is very clearly
explained.)

\iffalse
ADD PART: How much does he need to set aside today to do to pay \$1M in
scholarships 9 years from now?
\fi


\solution[\newpage]{ To pay out \$1 next year, Chuck needs $\$r$ now.  To
pay out \$1 in two years, he need $\$r^2$ now.  To pay out $\$1$ in $i$
years from now, he needs $\$r^i$.  So to pay out $\$a$ annually from now
(2002) until 2102 he needs
\[
\sum_{i=0}^{100} ar^i = a\frac{1-r^{101}}{1-r}
\]
dollars now.  So for \$100M today, Chuck can offer
\[
a = \frac{10^8(1-r)}{1-r^{101}}
\]
dollars annually.  This turns out to be slightly less than \$3.07M
annually---barely more than the \$3M he could give out and still have the
whole \$100M left at the end of a century.}

\ppart[9] Chuck would like to grant \$4M annually until 2102, but he
realizes that the \$100M available is not enough to do this.  So he
decides to hold off on awarding scholarships for $d$ years until the
\$100M, earning 3\% annually, has grown enough to award \$4M in annual
scholarships for the remaining years until 2102.  How many years must
Chuck wait before he can start awarding these scholarships?  Find a closed
form formula in terms of $r$ for the number of years, $d$, that Chuck must
wait; you do not have to evaluate the formula.  (Full credit for a formula
that evaluates to the right answer.  Partial credit for an incorrect
formula will only be considered when it is very clearly explained.)

\solution[\newpage]{Paying \$4M/year starting in $d$ years until 2102
requires setting aside
\[
\sum_{i=d}^{100} 4Mr^i
\]
dollars now.  This sum is
\begin{equation*}
4M [\sum_{i=0}^{100} r^i - \sum_{i=0}^{d-1} r^i] =
4M[\frac{1- r^{101}}{1-r} - \frac{1 - r^{d}}{1-r}] =
     \frac{4M}{1-r}(r^d - r^{101}).
\end{equation*}
So with \$100M, it is necessary and sufficient that
\begin{align*}
100M \ge  &\frac{4M}{1-r}(r^d - r^{101})\\
25 \ge & \frac{r^d - r^{101}}{1-r}\\
25(1-r) \ge & r^d - r^{101}\\
25(1-r) + r^{101} \ge & r^d\\
\ln (25(1-r) + r^{101}) \ge & d \ln r, \\
\frac{\ln (25(1-r) + r^{101})}{\ln r} \le & d.  &  \text{($\ln r$ is negative)}
\end{align*}
Using a calculator (not required for this Quiz), it turns out that this
lower bound on $d$ is $\approx 8.46$, so Vest must wait 9 years.}

\eparts

\end{examproblem}


\iffalse

\begin{examproblem}{15}
Chuck Vest is planning to set aside \$100M of MIT endowment funds in the
year 2002 so that MIT can eventually start awarding \$4M in annual student
scholarships and continue until 2102.  Assuming Chuck can count on earning
a 3\% annual return on invested funds, how many years should he wait
before he can start awarding these scholarships?  Find a closed form
formula for the number of years; you do not have to evaluate the formula.
(Full credit for a formula that evaluates to the right answer.  Partial
credit for an incorrect formula will only be considered when it is very
clearly explained.)

\solution[\newpage]{Paying \$4M/year starting in $d$ years for until 2102
costs $\sum_{i=d}^{101} 4Mr^i$ in today's dollars.  This sum is
\begin{equation*}
4M [\sum_{i=0}^{101} r^i - \sum_{i=0}^{d-1} r^i] =
4M[\frac{1- r^{102}}{1-r} - \frac{1 - r^{d}}{1-r}] =
     \frac{4M}{1-r}(r^d - r^{102})
\end{equation*}
so with \$100M, he needs
\begin{align*}
100M =  &\frac{4M}{1-r}(r^d - r^{102})\\
25 = & \frac{r^d - r^{102}}{1-r}\\
25(1-r) =& r^d - r^{102}\\
r^d = & 25(1-r) + r^{102}\\
d = & \frac{\ln (25(1-r) + r^{102})}{\ln r}.
\end{align*}
Using a calculator, it turns out that $d \approx 8.5$, so Vest must wait 9
years.}

\end{examproblem}

\fi

%% NEWPAGE--------------------------------------------------
\instatements{\newpage}

\begin{examproblem}{20}
Recall that for functions $f,g$ on the natural numbers, $\naturals$, $f
= O(g)$ iff
\begin{equation}\label{Oh}
\exists c \in \naturals\, \exists n_0 \in \naturals\,
\forall n \geq n_0\quad c \cdot g(n) \geq \abs{f(n)}.
\end{equation}

For each pair of functions below, determine whether $f = O(g)$ and whether
$g = O(f)$.  In cases where one function is O() of the other, indicate the
\emph{smallest natural number}, $c$, and for that smallest $c$, the
\emph{smallest corresponding natural number $n_0$} ensuring that
condition~(\ref{Oh}) applies.

\begin{problemparts}

\problempart[6] $f(n) = n^2, g(n) = 3n$.

$f = O(g)$ \hspace{.5in}YES \hspace{.5in}NO \hspace{.5in} 
If YES, $c =$ \brule{.5in}, $n_0$ = \brule{.5in}

\solution{NO.}

$g = O(f)$ \hspace{.5in}YES \hspace{.5in}NO \hspace{.5in} 
If YES, $c =$ \brule{.5in}, $n_0$ = \brule{.5in}

\solution[\vspace{0.7in}]{YES, with $c = 1$, $n_0 = 3$, which works
because $3^2 = 9$, $3 \cdot 3 = 9$.}

\problempart[7] $f(n) = (3n - 7) / (n + 4), g(n) = 4$

$f = O(g)$ \hspace{.5in}YES \hspace{.5in}NO \hspace{.5in} 
If YES, $c =$ \brule{.5in}, $n_0$ = \brule{.5in}

\solution{YES, with $c = 1, n_0 = 0$  (because $\abs{f(n)}< 3$).}

$g = O(f)$ \hspace{.5in}YES \hspace{.5in}NO \hspace{.5in} 
If YES, $c =$ \brule{.5in}, $n_0$ = \brule{.5in}

\solution[\vspace{0.7in}]{YES, with $c =2, n_0 = 15.$

Since $\lim_{n \to \infty} f(n) = 3$, the smallest possible $c$ is 2.
For $c = 2$, the smallest possible $n_0 = 15$ which follows from the
requirement that $2f(n_0) \ge 4$.}

\iffalse
\problempart[5] $f(n) = 2^{(n + 2 \sin(n))}, g(n) = 2^n$

$f = O(g)$ \hspace{.5in}YES \hspace{.5in}NO \hspace{.5in} 
If yes, $c =$ \brule{.5in} $n_0$ = \brule{.5in}

$g = O(f)$ \hspace{.5in}YES \hspace{.5in}NO \hspace{.5in} 
If yes, $c =$ \brule{.5in} $n_0$ = \brule{.5in}

\vspace{.7in} 

\solution{
$f = O(g)$    YES

$c = 4, n_0 = 0$    (because $2 \sin (n)$ contributes at worst $-2$ to the power)

$g = O(f)$    YES

$c = 4, n_0 = 0$    (because the $2 \sin (n)$ contributes at worst $+2$ to the power)
}

\fi

\problempart[7] $f(n) = 1 + (n \sin(n\pi/2))^2, g(n) = 3n$

$f = O(g)$ \hspace{.5in}YES \hspace{.5in}NO \hspace{.5in} 
If yes, $c =$ \brule{.5in} $n_0$ = \brule{.5in}

\solution{NO, because $f(2n)=1$, which rules out $g =
O(f)$ since $g=\Theta(n)$.}

$g = O(f)$ \hspace{.5in}YES \hspace{.5in}NO \hspace{.5in} 
If yes, $c =$ \brule{.5in} $n_0$ = \brule{.5in}

\solution{NO, because $f(2n+1) = n^2+1 \neq O(n)$ which rules out
$f = O(g)$.}

\end{problemparts}

\end{examproblem}


%% NEWPAGE--------------------------------------------------
\instatements{\newpage}

\begin{problem}[20]
Theory Hippo received a mysterious bag in the mail.  When he opened the
bag he found that it contained 100 6-sided dice and a note that said that
99 of the dice were fair, but one always throws a 6.  Theory Hippo decides
to experiment with the contents of the bag by pulling a die out of the bag
at random, throwing it $k$ times and then putting it back.  Call this
experiment $X(k)$.


%% A bag contains $1000$ nickels, of which $999$ are regular (fair)
%% nickels and $1$ is a two-headed nickel. 

\begin{problemparts}
\problempart[5]
Theory Hippo decides perform $X(10)$.
\begin{itemize}
\iffalse

\item Let $a$ be the probability that Theory Hippo gets 10 sixes given
that he pulled out the unfair die.  What is the value of $a$?

\solution[\vspace*{3cm}]{
\[
a =1.
\]
}
\fi

\item Let $a$ be the probability that Theory Hippo gets $10$ sixes given
that he pulled out a fair die.  What is the value of $a$?

\solution[\vspace*{3cm}]{
\[
a = \paren{\frac{1}{6}}^{10} = 6^{-10}.
\]
}

\item Let $b$ be the probability that Theory Hippo gets 10 sixes when he
performs X$(10)$.  What is the value of $b$?  You may (but are not
required to) express $b$ in terms of $a$ above.

\solution[\vspace*{3cm}]{
\[
b = \paren{\frac{1}{100}} +\paren{\frac{99}{100}}a
\]
}

\end{itemize}

\problempart[7] Theory Hippo has just performed $X(10)$ and ended up
getting 10 sixes!  Let $c$ be the probability that he pulled out the
unfair die, given that he got 10 sixes.  What is the value of $c$?  You
may (but are not required to) express $c$ in terms of $a$ and/or $b$.

\solution[\newpage]{Let $A$ be the event that Theory Hippo pulled out the
unfair die.  Let $B$ be the event that Theory Hippo got $10$ sixes.  Then:
\begin{align*}
c = & \prcond{A}{B}\\
  \eqdef & \frac{\pr{A \intersect B}}{\pr{B}}\\
  = & \frac{\pr{A}\prcond{B}{A}}{\pr{B}} & \text{(Product Rule)}\\
  = & \frac{(1/100)\cdot 1}{b} = \frac{1}{100b}.
\end{align*}
}

% OLD VERSION
% \problempart[8] Theory Hippo's assistant, performs X$(10)$, and ends
% up getting $10$ sixes too. She gets so excited that she wants to keep
% on flipping \emph{the same coin} another $10$ times. Let $e$ be the
% probability that Alyssa will flip another $10$ heads with the same
% coin. Express $e$ in terms of $a$, $b$, $c$ and $d$ (not all variables
% need be present in your solution).


\problempart[8] Theory Hippo's assistant performs $X(20)$ and reports that
the \emph{last} 10 of the 20 throws were sixes.  What is the probability,
$f$, that the \emph{first} 10 throws were also sixes?  You may (but are
not required to) express $f$ in terms of $a,b$, and/or $c$.

\solution[\vspace*{3cm}]{
\[
f = c + \frac{1-c}{6^{10}}.
\]

The previous reasoning about the first 10 throws applies equally to the
second 10 of 20, since successive throws are assumed to be independent.
So the assistant has pulled out the unfair die with probability $c$, and a
fair die with probability $1-c$.  Therefore, the probability of getting
another $10$ heads is
\[
c + (1-c)\cdot a =  c + \frac{1-c}{6^{10}}.
\]

Another way to approach this problem is by defining the following events:
\begin{align*}
B \eqdef & \text{the first 10 throws were sixes,}\\
L \eqdef & \text{the last 10 throws were sixes,}\\
F \eqdef & \text{the fair dice was chosen.}\\
\end{align*}
We just observed that
\begin{equation}\label{BL}
b \eqdef \pr{B} = \pr{L}.
\end{equation}

Note that we cannot assume $\pr{B \cap L} = \pr{B}\pr{L}$, that is, that
$B$ and $L$ are independent.  They are not: if you know there are 10 sixes
already, it increases the likelihood that it was the unfair dice that was
selected, and thus increases the chance of another 10 sixes.  However,
they are \emph{conditionally} independent depending on which die was
selected.  That is, given that the fair die was picked, then the outcomes
of the first 10 rolls are independent of the second 10:
\begin{equation}\label{BLF}
\prcond{B \intersect L}{F} = \prcond{B}{F}\cdot \prcond{L}{F}
\end{equation}
Likewise, given that the unfair die was picked, the outcomes of the first
10 and second 10 rolls are \emph{vacuously} independent, since in this
case every outcome has probability 0 or 1.
\begin{equation}\label{BLFbar}
\prcond{B \intersect L}{\bar{F}} = \prcond{B}{\bar{F}}\cdot \prcond{L}{\bar{F}}.
\end{equation}
So now we can calculate:
\begin{align*}
f \eqdef & \prcond{B}{L}\\
  \eqdef & \frac{\pr{B \cap L}}{\pr{L}}\\
  \eqdef & \frac{\pr{B \cap L}}{b} & \text{(by~(\ref{BL}))}\\
  = & \frac{\prcond{B \cap L}{F} \cdot \pr{F} + \prcond{B \cap L}{\bar{F}}
  \cdot \pr{\bar{F}}} {b} & \text{(Total Probability)}\\
  = & \frac{\prcond{B}{F}\cdot \prcond{L}{F} \cdot \pr{F} +
  \prcond{B}{\bar{F}}
   \cdot \prcond{L}{\bar{F}} \cdot \pr{\bar{F}}} {b} &
  \text{(by~(\ref{BLF}) \&~(\ref{BLFbar}))}\\
  = & \frac{a^2 \cdot \frac{99}{100} + 1^2 \cdot \frac{1}{100}}{b}\\
  = & \frac{99a^2}{100} + \frac{1}{100b}.
\end{align*}

Common errors on this problem included assuming that the first 10 rolls
and last 10 rolls \emph{are} independent without conditioning on which die
was chosen (fair or unfair).  Another common error was trying to apply the
law of total probability directly to ``$B\mid L$,'' leading to
the
\begin{falseclm*}
\[
\prcond{B}{L} = \prcond{B}{L \cap F} \cdot \pr{F}
     + \prcond{B}{L \cap \bar{F}} \cdot \pr{\bar{F}}
\]
\end{falseclm*}
The correct claim requires that the events $F$ and $\bar{F}$ also be
conditioned on the event $L$:
\[
\prcond{B}{L} = \prcond{B}{L \cap F} \cdot \prcond{F}{L}
     + \prcond{B}{L \cap \bar{F}} \cdot \prcond{\bar{F}}{L}.
\]
}
\end{problemparts}
\end{problem}


\iffalse
%% NEWPAGE--------------------------------------------------
\instatements{\newpage}
% From Nikos, 11.02

\begin{examproblem}{25}

There is a course---not 6.042, naturally---in which $10 \%$ of
the assigned problems contain errors.  If you pick a random problem
and send an email to your TA and your Lecturer asking whether the
problem has an error, then \emph{the TA's reply will be correct $80\%$
of the time}.  This $80 \%$ accuracy holds regardless of whether or
not a problem has an error.  Likewise, \emph{the Lecturer's reply will be
correct with only $75 \%$ accuracy}.  (This is consistent with the view
that Lecturers are chosen for their theatrical personalities, not
their mastery of the material \texttt{:-)}

Furthermore, the TA and Lecturers tend to be confused by different kinds
of problems.  The net result of this is that \emph{the correctness of the
lecturers' answer and the TA's answer are independent of each other,
regardless of whether there is an error}.

\iffalse
\emph{ Furthermore, the TA and
the Lecturer don't communicate with each other, before they give you an
answer and they cannot read each other's reply.} So, \emph{the probability
that both are correct is equal to the product of the probabilities that
the TA is correct and the Lecturer is correct.}
\fi

%Is the event that ``the TA says that there is an error'', independent
%of the event that ``the lecturer says that there is an error''?

\begin{problemparts}
\problempart[8]
Suppose you receive an email from your TA that says the problem has an
error.  Do the odds that the Lecturer's email will say that the problem
has an error \emph{increase, decrease or stay the same}?  Briefly explain
your answer without resorting to formulas.

\solution[\vspace{2in}]{ 
The odds increase.

Because the TA is usually right, when the TA says that the problem has an
error, the likelihood that there really is an error is increased.

But the lecturer is also usually right, so increasing the likelihood of
there \emph{being} an error also increases the likelihood that the
lecturer will \emph{report} an error.}

For the following parts, designate events as follows:
\begin{eqnarray*}
T & \eqdef & \mbox{``the TA's email says the problem has an error,''}\\
L & \eqdef & \mbox{``the Lecturer's email says the problem has an error.''}\\
E & \eqdef & \mbox{``the problem has an error,''}
\end{eqnarray*}

%We verify this informal argument by actually calculating the probability
%of each of these events and their intersection, and then observing that
%the probability that the two events occur is different from the product of
%the probabilities.

\problempart[8]
Using $T$, $L$ and $E$ translate the sentences in italics
into probability notation.  For example, the sentence ``the
probability that $A$ does not occur is $p$'' would translate to
$\pr{\bar{A}} = p$.

\solution[\vspace{2in}]{
%The assumptions above tell us:
\begin{align}
%\pr{E}        = & \frac{10}{100} = \frac{1}{10},\label{E10}\\
\prcond{T}{E} = & \prcond{\bar{T}}{\bar{E}} = \frac{80}{100} =
     \frac{4}{5},\label{TE}\\
\prcond{L}{E}  = & \prcond{\bar{L}}{\bar{E}}
       = \frac{75}{100} = \frac{3}{4}\label{LE}.
\end{align}

%Also, $T$ and $L$ are independent given $E$, and given $\bar{E}$:
\begin{align}
\prcond{T \intersect L}{E}  = & \prcond{T}{E} \prcond{L}{E}\label{TLE}\\
\prcond{T \intersect L}{\bar{E}}  = & \prcond{T}{\bar{E}}
                      \prcond{L}{\bar{E}}  \label{TLbarE}. 
\end{align}
}
%Note that while we know that $T$ and $L$ are independent \emph{given} $E$
%or \emph{given} $\bar{E}$, we will show that they are not independent by
%themselves.  In fact, we will show:

%%\begin{claim*}
%\[
%\pr{L \intersect T} > \pr{L}\pr{T}.
%\]
%%\end{claim*}


\problempart[9] What is the probability that \emph{both} the Lecturer and TA
report an error?

\solution[\vspace{2in}]{

%$\pr{L \cap T}$.
% \begin{align*}
% \pr{T} = & \pr{T \cap E} + \pr{T \cap \bar{E}}
%         & \text{(Law of Total Probability)}\\
%  = & \prcond{T}{E} \pr{E}  + \prcond{T}{\bar{E}} \pr{\bar{E}}
%         & \text{(Product Rule)} \\
%  = & \prcond{T}{E} \pr{E}  + (1- \prcond{\bar{T}}{\bar{E}})(1- \pr{E})
%         & \text{(Complement Rule)} \\
%  = & \prcond{T}{E} \pr{E}  + (1- \prcond{T}{E})(1- \pr{E})
%         & \text{(by~(\ref{TE}))} \\
%  = & \frac{4}{5} \frac{1}{10} + (1 - \frac{4}{5})(1 - \frac{1}{10})
%         = \frac{13}{50}, & \text{(by~(\ref{TE}) and~(\ref{E10}))}\\
% \end{align*}

% A similar argument proves that
% \begin{equation}
% \pr{L} =  \pr{L \cap E} + \pr{L \cap \bar{E}}
%   = \frac{3}{4} \frac{1}{10} + (1 -\frac{3}{4})(1 - \frac{1}{10}) = \frac{3}{10}.
% \end{equation}

% Finally,

\begin{align*}
\pr{L \cap T} = & \pr{L \cap T \cap E} + \pr{L \cap T \cap \bar{E}}
        & \text{(Law of Total Probability)}\\
= & \prcond{L \cap T}{E} \pr{E} + \prcond{L \cap T}{\bar E} \pr{\bar E}
        & \text{(Product Rule)} \\
= & \prcond{L}{E}      \prcond{T}{E}       \pr{E} + 
      \prcond{L}{\bar{E}} \prcond{T}{\bar{E}} \pr{\bar E} &
        \text{(by~(\ref{TLE}) and~(\ref{TLbarE}))}\\
= & \frac{3}{4} \cdot \frac{4}{5} \cdot \frac{1}{10}
        + (1 - \frac{3}{4}) (1 - \frac{4}{5}) (1 - \frac{1}{10}) =
        \frac{105}{1000} = 0.105. & \text{(by~(\ref{LE}) and~(\ref{TE}))}
\end{align*}
}
% which is higher than 
% \[
% \pr{L}\pr{T} = \frac{3}{10} \cdot \frac{13}{50} = .078.
% \]
% }
\end{problemparts}
\end{examproblem}
\fi

%% NEWPAGE--------------------------------------------------
\instatements{\newpage}

% \problemdata     
% {}           
% {ALL COUNTING METHODS}              
% {F01 final exam} 		
% {}
% {}

\begin{examproblem}{25}
We are going to classify different counting problems by figuring
out which ones have the same formula.  Here is a set of six formulas.

\begin{center}
\begin{tabular}{rl}
$n^m$:       &\brule{1in}\\
$m^n$:       &\brule{1in}\\
$P(n,m)$:    &\brule{1in}\\
$C(n-1+m,m)$:&\brule{1in}\\
$C(n-1+m,n)$:&\brule{1in}\\
$2^{mn}$:      &\brule{1in}\\
\end{tabular}
\end{center}

For each problem part below, write its label---(a),(b),\dots---on the line
next to the corresponding formula above.

\solution{
\begin{align*}
n^m: & b d\\
m^n: & f h \\
P(n,m): & c j \\
C(n-1+m,m): & a \\
C(n-1+m,n): & e \\
2^{mn}: & g i\\
\end{align*}
}

\begin{problemparts}

\problempart[2] Number of arrangements of $m$ indistinguishable balls in
$n$ distinguishable urns.

\problempart[2] Number of arrangements of $m$ distinguishable balls in $n$
distinguishable urns.

\problempart[2] Number of $m$ letter words from an alphabet of size $n$,
with no letter used more than once ($m \leq n$).

\problempart[2] Number of $m$ letter words from an alphabet of size $n$,
where any letter can be repeated any number of times.

\problempart[2] Number of sequences of $n$ indistinguishable red balls and
$m-1$ indistinguishable blue balls.

\problempart[3]
Number of matrices of size $\sqrt{n} \times \sqrt{n}$ with $m$
possible values for each entry.  (Assume $n$ is a perfect square.)

\problempart[3]
Number of possible subsets of A, where $\card{A}=nm$.

\problempart[3]
Number of functions from set $A$ to $B$ where $\card{A}=n$ and $\card{B}=m$.

\problempart[3] Number of relations from set $A$ to $B$ where $\card{A}=n$
and $\card{B}=m$.

\problempart[3]
Number of injections from set $A$ to $B$ where $\card{A}=m$ and
$\card{B}=n$, and $m \leq n$.

\iffalse

\problempart[2]
Number of natural number solutions of the equation $x_1 + x_2 + x_3
\cdots x_n = m$, where $m$ is a non-negative integer.  (A solution is
a non-negative integer vector of values for $x_1,x_2,\cdots x_n$.)

\problempart[2]
Number of permutations of $m$ indistinguishable stars and
$n-1$ indistinguishable bars.
\fi

\end{problemparts}
\end{examproblem}


%% NEWPAGE--------------------------------------------------
\instatements{\newpage}

% \problemdata                                                             
% {Pigenhole/Counting} % latex-friendly label for the prob.
% {STARS \& BARS, PIGEONHOLE} % The topic(s) of the problem content.  
% {stimulated by S01 Final, 4, suggested F02 Q2 by Tina Wang} 
% {} % Usage (list ones you are aware of). 
% {ARM, 11/11/02} % Last revision info (author, date).   

\begin{examproblem}{20} 

Let $S \eqdef \set{0,1,\dots,9}^{90}$ be the set of all sequences of
length 90 consisting of digits $\set{0,1,\dots,9}$.  Two
sequences, $s_1,s_2 \in S$ are said to have the \emph{same digit
distribution} iff $s_1$ has the same of number of occurrences of digit
$j$ as $s_2$, for each $j \in \set{0,\dots,9}$.

\bparts

\ppart[7] Describe a bijection between digits distributions and arrangements
of ``stars \& bars.''

\solution[\vspace{3in}]{There is a bijection between digit distributions
and permutations of 90 stars and 9 bars.  The 9 bars divide the 90 stars
into 10 blocks, with the number of stars in the $i$th block equal to the
number of occurrences of digit $i$ in the distribution.}


\ppart[7]\label{digita} Give a closed formula, possibly also involving
factorials and binomial coefficents, for the number, $g$, of possible
digit distributions.

\solution[\vspace{0.5in}]{the number of permutations of 90 stars and 9 bars is
\[
g = \binom{99}{9}.
\]
}

\ppart[6] Let $n$ be the smallest number such that any set of $n$
sequences in $S$ is sure to contain four different sequences with the same
digit distribution.  Give a closed formula, possibly also involving
factorials and binomial coefficents, for $n$.  You may write your formula
in terms of $g$ in part~(\ref{digita}).

\solution[\vspace{0.5in}]{

\iffalse
CORRECT ANSWER IS $3(g-10) + 10 +1 = 3g-19$.  ADD EXPLANATION.  EXPLAIN
$3g+1$ would work for multisets of sequences.
\fi

The correct answer, which a few students got and most of the staff did
not, is $n = (3(g-10) +1)+10 = 3g-19$.  This is a problem about the
Generalized Pigeonhole Principle.  Here the pigeons are the $10^90$
possible sequences of 90 digits and the holes are the $g$ possible
digit distributions.  For any digit $d$, there is only one possible
sequence ($d^90$) that will fall into the hole with the distribution
d=90 so those 10 holes can only ever have one pigeon in them.  So we
subtract them from $g$, the total number of holes.  Then if we put 3
pigeons in the other $g-10$ holes and 1 pigeon in each of these 10
holes, we still need one more pigeon (sequence) to guarantee that one
hole will have 4 pigeons.

The intended answer was $n = 3g+1$, which would be correct if we allowed
the same sequence to occur several times, \viz if we had asked for the
smallest $n$ ensuring that any \emph{multiset} of $n$ sequences had four
elements with the same distribution.  By the Generalized Pigeonhole
Principle, in any multiset of $m \ge 3g+1$ occurrences of sequences in
$S$, there will be at least $\ceil{m/g} \ge \ceil{(3g+1)/g} = 4$
occurrences of sequences with same distribution.  Moreover, there is a
multiset of $3g$ occurrences in which no distribution occurs 4 times,
namely, choose a multiset in which each distribution occurs exactly 3
times.

Actually, for either of these answers to be correct, it's also obviously
necessary that $\card{S} \ge 3g-19$ or $3g+1$, respectively.  But it's
easy to check that $\card{S} = 10^{90}$ is indeed much larger than
$3C(99,9)+1$.}

\iffalse

%%extra parts for the FINAL??:  
\ppart Suppose instead of 4 sequences with the same distribution, we
wanted to guarantee $10^{100}$ sequences with the same distribution.
Show that $n = 10^{90} + 1$.

\solution{
The number of sequences is $10^{90} < 10^{100}$, so there aren't enough
sequences to yield the required number of digit distributions.  Hence only
sets of more than the number of sequences, of which there are none of
course, will, vacuously, have the required number of distributions.
}

\ppart Suppose instead of 4 sequences with the same distribution, we
wanted to guarantee $10^{9}$ sequences with the same distribution.  Show
that there is such an $n < 10^{90}$.

\solution{Just need to show that
\[
10^{9} (\text{\# of digit distributions}) + 1 \le (\text{\# of
sequences}).
\]

Can verify this using Stirling's approximation to estimate \binom{99}{9};
somewhat extended but routine approximate calculation.  Probably also not
hard to verify w/o Stirling.}
\fi

\end{problemparts}
\end{examproblem}

\end{document}
