\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 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.)

\solution[\newpage]{An annuity paying \$$a$ annually from 2002 until 2102
could be funded for $\sum_{i=0}^{100} ar^i$ in today's dollars.  This sum is
\[
a\frac{1-r^{101}}{1-r},
\]
so for \$100M, Chuck can offer
\[
a = \frac{10^8(1-r)}{1-r^{101}}
\]
dollars annually.  This turns out to be slight 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 for until 2102
costs $\sum_{i=d}^{100} 4Mr^i$ in today's dollars.  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{($\log r$ is negative)}
\end{align*}
Using a calculator, 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^2  (\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}}.
\]
}
\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{center}
\begin{tabular}{rl}
$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{tabular}
\end{center}
}

\begin{problemparts}

\problempart[2]
Number of ways of putting $m$ indistinguishable balls into $n$
distinguishable urns.

\problempart[2]
Number of ways of putting $m$ distinguishable balls into $n$
distinguishable urns.

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

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

\problempart[2]
Number of ways of lining up $n$ red balls and $m-1$ 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 $|A|=nm$.

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

\problempart[3]
Number of relations from set $A$ to $B$ where $|A|=n$ and $|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}]{$n = 3g+1$.

By the Generalized Pigeonhole Principle, in any set of $m \ge n$ sequences
in $S$, there will be at least $\ceil{m/g} \ge \ceil{n/g} = 4$ sequences
with same distribution.

Actually, for this answer to be correct, it's also obviously necessary
that $\card{S} \ge 3g+1$.  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}
