\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 Appendix 
  with standard definitions.
  \item 
  There are five (5) problems totaling 100 points. Total time is 110 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[conflict quiz, Wednesday 11/13]{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
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 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 until a year when 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 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}^{100} 4Mr^i$ in today's dollars, where $r \eqdef
1/1.03$.  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, he needs
\begin{align*}
100M =  &\frac{4M}{1-r}(r^d - r^{101})\\
25 = & \frac{r^d - r^{101}}{1-r}\\
25(1-r) =& r^d - r^{101}\\
r^d = & 25(1-r) + r^{101}\\
d = & \frac{\ln (25(1-r) + r^{101})}{\ln r}.
\end{align*}
Using a calculator, it turns out that $d \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, where $r \eqdef
1/1.03$.  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}

\iffalse
%% NOTE: Perhaps recycle in FINAL withalbertmeyer instead of almeyer

% \problemdata     
% {}           
% {MULTINOMIAL COEFFICIENTS, AND INCLUSION-EXCLUSION}              
% {parts (a) (b) F99, Practice Final} 		
% {}
% {}

\begin{examproblem}{20}

Consider the seven letter word \emph{almeyer}.

\begin{problemparts}

\problempart[5]
How many different sequences of these seven letters are
there? \brule{1in}

\solution[\vspace{1in}]{$\binom{7}{1,1,1,2,1,1} = 7!/2!$}


\problempart[5]
How many such sequences are there that do not contain
either of the words \emph{eye} or \emph{ram}? \brule{1in} 

\solution[\vspace{1in}]{7!/2! - 5! - 5!/2! + 3!}

\problempart[10]
Clearly explain your counting argument for part (b)

\solution{
\begin{eqnarray*}
\mbox{Arrangements with eye: use} \set{eye,a,l,m,r} & = & 5!\\
\mbox{Arrangements with ram: use} \set{ram,l,e,y,e} & = & 5!/2!\\
\mbox{Arrangements with ram and eye: use} \set{ram,eye,l} & = & 3!\\
\mbox{Arrangements with neither ram nor eye}
      & = & 7!/2! - 5! - 5!/2! + 3! = 2346.
\end{eqnarray*}
}

\end{problemparts}
\end{examproblem}
\fi

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

\begin{examproblem}{20}
Recall that $f(n) = O(g(n))$ means "There exists a $c$ and $n_0$ such
that for all $n \geq n_0, c \cdot g(n) \geq f(n)$."

For each pair of functions below, determine whether $f(n) = O(g(n))$
and whether $g(n) = O(f(n))$.  In cases where a function is Big-O
another function, provide a natural number $c$ and the corresponding
natural number $n_0$.

\begin{problemparts}

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

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

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

\vspace{.7in} 

\solution{
$f(n) = O(g(n))$    NO

$g(n) = O(f(n))$    YES

$c = 1$, $n_0 = 3$ (because $3^2 = 9$, $3 \cdot 3 = 9$)
}

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

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

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

\vspace{.7in} 

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

$c = 2, n_0 = 15$    (turns out to be a simple linear equation)

$c = 1, n_0 = 0$     (easy to see that the f(n) is less than 3)

$g(n) = O(f(n))$    YES

$c = 1, n_0 = 5$
}

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

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

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

\vspace{.7in} 

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

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

$g(n) = O(f(n))$    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(n) = O(g(n))$ \hspace{.5in}YES \hspace{.5in}NO \hspace{.5in} 
If yes, $c =$ \brule{.5in} $n_0$ = \brule{.5in}

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

\vspace{.7in} 

\solution{

$f(n) = O(g(n))$    NO

$g(n) = O(f(n))$    NO

}

\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 concieved of an experiment X$(k)$ which consists of pulling a
dice out of the bag at random, throwing it $k$ times and then putting
it back.

%% 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}
\item Let $a$ be the probability that Theory Hippo gets $10$ sixes
given that he pulled out the unfair dice. What is the value of $a$?

\solution[\vspace*{3cm}]{
\begin{eqnarray*}
a&=&1
\end{eqnarray*}
}


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

\solution[\vspace*{3cm}]{
\begin{eqnarray*}
b&=&6^{-10}
\end{eqnarray*}
}

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

\solution[\vspace*{3cm}]{
\begin{eqnarray*}
c&=&\paren{\frac{1}{100}}a+\paren{\frac{99}{100}}b
\end{eqnarray*}
}

\end{itemize}

\problempart[7] Theory Hippo has just performed X$(10)$ and ended up
getting $10$ sixes! Let $d$ be the probability that he pulled out the
the unfair dice, given that he got 10 sixes. Express $d$ in terms of
$a$, $b$ and $c$ (not all variables need be present in your solution).

\solution[\newpage]{
Let $A$ be the event that Theory Hippo pulled out the two-headed coin. Let $B$ be
the event that Theory Hippo got $10$ heads. Then:
\[
d~=~Pr(A|B)~ =~ \frac{Pr(A)}{Pr(B)}Pr(B|A)~ =~ \frac{1/100}{c}\cdot 1~ =~ \frac{1}{100c}
\]
}

% 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 last 10 throws were sixes. What is the probability that the
first 10 throws were also sixes? Express $e$ in terms of $a$, $b$, $c$
and $d$ (not all variables need be present in your solution).

\solution[\vspace*{3cm}]{SAME ANSWER, BUT REWRITE SOLUTION: Alyssa has
pulled out the two-headed coin with probability $d$, and a regular
coin with probability $1-d$. Therefore, the probability of getting
another $10$ heads is
\begin{eqnarray*}
d\cdot a + (1-d)\cdot b &=& d + (1-d)\cdot 6^{-10}
\end{eqnarray*}
}
\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.

\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

\solution{

\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{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
$d$ as $s_2$, for each $d \in \set{0,\dots,9}$.

\bparts

\ppart[14]\label{digita} Give a formula for the number of possible
digit distributions.

% \ppart[10]\label{digita} Describe a bijection between digit
% distributions and permutations of stars and bars. Give a formula for
% the number of possible digit distributions.

\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).  So
\[
k = \binom{99}{9},
\]
}


\ppart[6] What is the smallest number $n$ such that any set
of $n$ sequences in $S$ is sure to contain four different sequences with
the same digit distribution?  Give your answer in terms of $k$, where $k$
is the answer to part~(\ref{digita}).

\solution[\vspace{3in}]{
There are only a finite number, $k$, of digit distributions possible
(clearly $k \le 91^{10}$, since every digit distribution can be described
listing 10 numbers between 0 and 90, namely, the number of 0's, number of
1's,\dots.)  By the Generalized Pigeonhole Principle, if $n \ge 3k+1$,
there must be four strings with the same distribution.
}

\iffalse
\ppart[10]\label{digita} Explain why there is an integer $n>0$ such that
any set of at least $n$ sequences in $S$ is sure to contain four different
sequences with the same digit distribution.

\solution[\vspace{3in}]{
There are only a finite number, $k$, of digit distributions possible
(clearly $k \le 91^{10}$, since every digit distribution can be described
listing 10 numbers between 0 and 90, namely, the number of 0's, number of
1's,\dots.)  By the Generalized Pigeonhole Principle, if $n \ge 3k+1$,
there must be four strings with the same distribution.
}

\ppart[10] Write a closed form formula involving binomial coefficients for
the \emph{smallest} value for $n$ which will work in part~(\ref{digita}).

\solution[\vspace{3in}]{We need only find the number, $k$, of possible digit
distributions.  But 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).  So
\[
k = \binom{99}{9},
\]
and
\[
n = 3\binom{99}{9} + 1.
\]
}
\fi

\end{problemparts}
\end{examproblem}

\end{document}


%%%%%%%% EXTRA UNUSED PROBLEMS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\iffalse

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

\problemdata     
{Series of counting questions}           
{SIMPLE PIGEONHOLE, STARS AND BARS, GRAPHS, COMBINATIONS}              
{F97, practice final} 		
{parts (a) (b) F99, Practice Final}
{part (c) Rad 11/2002}
\begin{examproblem}{1}
\begin{problemparts}
\problempart[1] PIGEONHOLE
An assembly line produced 10001 cars which passed inspection and 19
which did not.  What is the largest $n$ for which there must have been
a run of $n$ consecutive cars that passed inspection?  \brule{1.0in}

\solution{501, by generalized pigeonhole}

\problempart[1] STARSNBARS
A bridge hand consists of 13 cards.  The {\em suit-distribution} of a
hand is the number of cards in each suit.  For example, one possible
suit-distribution is 4 spades, 3 hearts, 3 diamonds, and 3 clubs.  How
many suit-distributions are there?

\solution{This is equivalent to placing 13 balls (corresponding to each
card in a hand) to 4 bins (corresponding to each suit).  Thus the
number of distributions is $\binom{13 + 4 - 1}{4 - 1} = 560.$ }

\problempart[1]  COUNTING GRAPHS
%% made up by Rad (11/02)
How many directed graphs are there (self-loops permitted) on $n$
labelled vertices, that have exactly 5 edges?

\solution{There are $n^2$ possible edges, and $n^2 choose 5$ ways of
selecting edges to be in the graph (check tthis answer). Other
possibilities are, at elast 5 edges (add up the subsets), or exactl
$n-1$ edges (and perhaps a question asking whether or not counts the
number of tree? no because not necessarily connected)}

\end{problemparts}
\end{examproblem}
\fi


\iffalse

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

\problemdata     
{}           
{PIGEONHOLE PRINCIPLE}              
{F97, practice final} 		
{}
{}
\begin{examproblem}{1} PIGEONHOLE PRINCIPLE
%% NOTE: this is the same pigeonhole problem as covered in lecture
%% as the Ramsey Number R(3,3) problem

\begin{problemparts}

\problempart[1]
Six people communicate via radio frequency with one another. Each pair
of people choose one of {\bf two} available frequencies with which to
communicate.  Show that there is a subset of 3 people who are each
using the identical frequency with which to communicate with others in
the subset.

\solution{
Each person communicates with five other persons.  By the pigeonhole
principle, this person (say $a$) communicates with another three
persons (say $b$,$c$,and $d$) using the same frequency.  If either of
the pairs $(b,c), (b,d), (c,d)$ uses this frequency then we have three
persons using it to communicate with each other and we are done.  If
not, then the pairs $(b,c), (b,d), (c,d)$ all use the other frequency,
so we are done again.}


\problempart[1]
Now suppose there are seventeen people communicating via radio 
frequency with one another. Each pair
of people choose one of {\bf three} available frequencies with which to
communicate.  Show that there is a subset of 3 people who are each
using the identical frequency with which to communicate with others in
the subset.

\solution{ Now each person communicates with sixteen other people, 
and by pigeonhole uses the same frequency with at least six of them.
If any pair among these six persons uses that same frequency then we
are done.  If not, then these six persons communicate with one another
using two different frequencies so we are back in part (a) of the
problem.}  
\end{problemparts} 
\end{examproblem}
\fi

\iffalse

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

\problemdata                                                             
        {Pigenhole/Counting} % latex-friendly label for the prob.
        {PIGEONHOLE, COUNTING} % The topic(s) of the problem content.  
        {Rosen, Instructor's resource guide, page 357, exercise 38, page 356, exercise 32} % Source (if known)                                          
        {S01 Final, 4} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   

\begin{examproblem}{1} PIGEONHOLE
\begin{problemparts} 
\problempart[1] A professor teaching 6.042 gives a multiple choice
quiz that has 10 questions, each of which has 4 possible answers
(a,b,c,d). What is the \emph{minimum} number of students that must be
in the professor's class in order to guarantee that at least three
answer sheets must be identical? (assume that no answers are left
blank).  Justify your answer.

\solution{ There are $4^{10}$ possible answers. By the strong
pigeonhole principle, in order to have the desired property, we need
at least $2\cdot 4^{10}+1$ students.  }


\problempart[1] Let $s_1, s_2,\ldots, s_{101}$ be 101 strings of 1's
and 0's that are at most 9 digits long. Prove that there exist 2
strings, $s_i$ and $s_j$, with $i\neq j$, that contain the same number
of 0's and the same number of 1's. (For example, strings 110001001 and
101000110 contain the same number of 0's and the same number of 1's)
[Note: You actually need much fewer than 101 strings to prove the
above---you can give a proof using a lower number of strings if you
would like to (for equal credit).]

\solution{ We can associate a pair $(a,b)$ with each string, where $a$
is the number of 0's and $b$ is the number of 1's. There are \emph{at
most} 100 such pairs (actually, the constraint about the length of the
string implies that there are fewer than 100). We can consider the
pairs to be the holes and the strings to be the pigeons. Since there
are more pigeons than holes, one hole must have at least 2
pigeons. Two strings that are associated with the same pair will have
the same number of 0's and the same number of 1's.
  
If we take the constraint about the length into account, then we see
that there can be only 55 $(a,b)$ pairqs: for each possible length
$i\in[0\ldots 9]$ there are $i+1$ possibilities for the number of
$0$'s (or 1's, of course). Thus, the total number of \emph{legal}
pairs $(a,b)$ is
\[
\sum_{i=0}^{9}{i+1}=55
\]
Since there are (much) more pigeons thaqn holes, one hole will have at
least 2 pigeons.  }
\end{problemparts}
\end{examproblem}
\fi


\iffalse

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

\problemdata     
{S01-PS6-2}           
{PIGEONHOLE PRINCIPLE}              
{}
{S99-PS7, S01-PS6} 		
{S01 Karger}
\begin{examproblem}{1} ALREADY USED IN ONLINE READING PROBLEMS
Below is a list of properties that a group of people might possess.
For each property, either give the minimum number of people that must
be in a group to ensure that the property holds, or else indicate that
the property need not hold even for arbitrarily large groups of
people.  Assume that every year has exactly 365 days; ignore leap
years.  No proofs are required.

\begin{problemparts}

\problempart[1] 
At least 2 people were born on the same day of the year.

\solution{This property holds for every group of 366 or more people.}

\problempart[1]
At least 2 people were born on January 1.

\solution{This property need not hold, even for arbitrarily large
groups of people.}

\problempart[1] 
At least 3 people were born on the same day of the week.

\solution{
This property holds for every group of 15 or more people.
}

\problempart[1]
At least 4 people were born in the same month.

\solution{
This property holds for every group of 37 or more people.
}

\problempart[1]
At least 2 people were born exactly one week apart.

\solution{This property need not hold.  For example, everyone might be
born on the same day of the year.
}

\problempart[1] 
At least 9 people were born on a weekend or at least 11 people were born during
the week.

\solution{This property holds for every group of at least $(9-1) +
(11-1) + 1 = 19$ or more people.}

\problempart[1] 
At least 2 people were born on the same day of the year or else 2 people were
born exactly one week apart.

\solution{There are two interpretations of this question, which differ
on whether, say, people born on Dec 31 and Jan 6 were born a week
apart.  If such ``wraparound'' is considered, then the answer is 183
people.  If ``wraparound'' is ignored, then the answer is 184 people.
}

\end{problemparts}

\end{examproblem}
\fi

\iffalse

%% NEWPAGE--------------------------------------------------
\instatements{\newpage}
 
\problemdata     
{}           
{PERMUTATIONS, STARSNBARS}
{}
{F99 final exam} 		
{F02 ktkohl instructor->untheoretically}
\begin{examproblem}{1}

Counting with Repetition.  Consider the letters in the word
``UNTHEORETICALLY''.

\begin{problemparts}
\problempart[1] 
How many distinguishable ways are there to rearrange the letters?

\solution{There are $15!$ ways to arrange 15 distinct letters, but we have two
Ts, two Ls, and two Es, so this overcounts by a factor of $2!$ for the Ts, $2!$
for the Ls, and $2!$ for the Es.  The correct answer is $\frac{15!}{2!2!2!}$}

\problempart[1]
How many distinguishable arrangements with all vowels consecutive?

\solution{Let the letter V represent the block of vowels, treated as a single
unit.  How many ways can we rearrange the letters NTHRTCLLYV?  There are $9!$
ways to arrange 9 distinct letters, but we have two Ts, and two Rs, so this
overcounts by a factor of $2!2!$.  So there are $\frac{9!}{2!2!}$ ways to
arrange the letters NTHRTCLLYV.  There are 7 vowels, including 2 Es, so there
are $\frac{7!}{2!}$ ways to arrange the vowels within the block V, so the
number of ways to arrange the letters with all the vowels consecutive is
$\frac{7!}{2!}\frac{9!}{2!2!}$.}

\problempart[1]
How many distinguishable arrangements with all vowels (including Y) in
alphabetical order?

\solution{star and bars?}
\end{problemparts}
\end{examproblem}
\fi

\iffalse

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

\problemdata      
        {?} % latex-friendly label for the prob.
        {Counting: STARS N BARS} % The topic(s) of the problem content.
        {?} % Source (if known)
        {Fall 2001, quiz 3} % Usage (list ones you are aware of).
        {Christos Kapoutsis, S02} % Last revision info (author, date).

\begin{examproblem}{1} HARD QUIZ QUESTION (Fall 01),
A juggler plans to juggle 15 rings for his final\'e---more than any
other circus performer has ever managed.  In his bag are 9 red rings,
11 blue rings, 13 white rings, and 15 rings striped with all three
colors.  He must select at least two of each kind of ring to be
patriotic.  An example of a patriotic choice of 15 rings would be: 2
red, 6 white, 3 blue and 4 striped.  How many different patriotic
choices are there for the 15 rings?

\solution{$120$.

This is a ``stars and bars'' problem: the same as asking how many ways
there are to arrange 15 stars (the rings) and three bars such that there
are at least two stars in each of the four groups (the kinds of rings)
delimited by the bars.  Reserving eight stars for this purpose leaves 7
stars, so there are
\[
\binom{3 + 7}{3} = \binom{10}{3}.
\]
Note that the initial number of each kind of ring available to
the juggler is irrelevant as long as there are at least 9 of each.
}
\end{examproblem}
\fi

\iffalse

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

\problemdata     
{}           
{counting, errors}              
{Friend of CEL} 		
{}
{}
%% 6.042 staffers,
%% I received the attached email message from a friend.  Locating the
%% error might make a good homework or classroom problem when we do
%% combinatorics.
%% Cheers,
%% Charles
\begin{examproblem}{1} 

FALSE COUNTING: NEED TO REWORD and FIGURE OUT THE SOLUTION!

I'm trying to calculate the number of possible combinations of hands
containing one pair.  I have two methods for doing this.  If I use
both methods where the hands have three cards (as you do in a poker
variant called "guts"), I get the same answer.  If i use both methods
for a standard 5-card poker hand, I get two different answers.  My
question is what error am I making and why aren't both methods right.

In my notation, choose(N, K) = N choose K = N! / ( (N-K)! * K! )


Method 1

A 5 card hand with only one pair consists of four ranks.  There are
choose(13,4) combos of ranks. Each of these ranks could be any of 4
suits, so 3 ranks have choose(4,1) different cards, and the fourth
rank has choose(4,2) different combos of cards.  Any of the 4 ranks
could be the pair, so multiply by 4.

\begin{verbatim}
total combos = choose(13,4) * choose(4,1) * choose(4,1) * choose(4,1)
* choose(4,2) * 4
total combos = 13!/(9! * 4!) * 4 * 4 * 4 * 6 * 4
total combos = (13 * 12 * 11 * 10)/(4 * 3 * 2) * 4 * 4 * 4 * 6 * 4
total combos = 13 * 12 * 11 * 10 * 4 * 4 * 4
total combos = 1,098,240
\end{verbatim}

Method 2

The pair could be any of 13 ranks. Each rank has choose(4,2) combos of
suits.  The third card could be any of 12 remaining ranks.  Each rank
has choose(4,1) different suits.  The fourth card could be any of 11
remaining ranks.  Each rank has choose(4,1) different suits.  The
fifth card could be any of 10 remaining ranks.  Each rank has
choose(4,1) different suits.

\begin{verbatim}
total combos = 13 * choose(4,2) * 12 * choose(4,1) * 11 * choose(4,1)
* 10 * choose(4,1)
total combos = 13 * 6 * 12 * 4 * 11 * 4 * 10 * 4
total combos = 13 * 12 * 11 * 10 * 4 * 4 * 4 * 6  <-- rearranging the
factors -- I am off by a factor of 6
total combos = 6,589,440
\end{verbatim}

OFF BY A FACTOR OF 6.

Which one is wrong? And what is wrong?

\solution{good question..}

\end{examproblem}
\fi


\iffalse

\problemdata     
{S01-PS5-2}           
{Summations}              
{S99-PS5, S01-PS5} 		
{S01 Karger}
proposed by George, 11/02


\begin{examproblem}

Find closed-form expressions for the following sums.

\begin{problemparts}

\iffalse

%\problempart
\[
\sum_{i=0}^n \frac{9^n - 7^n}{11^n}
\]

\solution {
Split the expression into two geometric series and then
apply the formula for the sum of a geometric series.

\begin{eqnarray*}
\sum_{i=0}^n \frac{9^i - 7^i}{11^i}
    & = &   \sum_{i=0}^n \left(\frac{9}{11}\right)^i -
        \sum_{i=0}^n \left(\frac{7}{11}\right)^i \\
    & = &   \frac{1 - \left(\frac{9}{11}\right)^{n+1}}{1 - \frac{9}{11}}
          - \frac{1 - \left(\frac{7}{11}\right)^{n+1}}{1 - \frac{7}{11}} \\
    & = &   - \frac{11}{2} \cdot \left(\frac{9}{11}\right)^{n+1}
        + \frac{11}{4} \cdot \left(\frac{7}{11}\right)^{n+1}
        + \frac{11}{4}
\end{eqnarray*}

}
\fi

\problempart
\[
\sum_{i=0}^{\infty} \sum_{j=0}^{\infty} \sum_{k=0}^{\infty} 2^{-(i +2j +3k)}
\]

\solution {
 Apply the formula for the sum of a geometric series three
times.

\begin{eqnarray*}
\sum_{i=0}^{\infty} \sum_{j=0}^{\infty} \sum_{k=0}^{\infty} 2^{-(i +2j +3k)}
    & = &   \sum_{i=0}^{\infty} 2^{-i} \cdot
        \left(\sum_{j=0}^{\infty} 2^{-2j} \cdot
        \left(\sum_{k=0}^{\infty} 2^{-3k} \right) \right) \\
    & = &   \sum_{i=0}^{\infty} 2^{-i} \cdot
        \left(\sum_{j=0}^{\infty} 2^{-2j} \cdot
        \frac{8}{7} \right) \\
    & = &   \sum_{i=0}^{\infty} 2^{-i} \cdot
        \frac{4}{3} \cdot \frac{8}{7} \\
    & = &   \frac{2}{1} \cdot \frac{4}{3} \cdot \frac{8}{7} \\
    & = &   \frac{64}{21}
\end{eqnarray*}
}

%\iffalse

\problempart
\[
\sum_{i=n+1}^{2n} i^2
\]

\solution {

This expression is the difference of two sums of squares, which can be
reduced to a closed form by a standard formula.

\begin{eqnarray*}
\sum_{i=n+1}^{2n} i^2
    & = &   \sum_{i=1}^{2n} i^2 - \sum_{i=1}^{n} i^2 \\
    & = &   \frac{(2n)(2n+\frac{1}{2})(2n+1)}{3} -
        \frac{n(n+\frac{1}{2})(n+1)}{3} \\
    & = &   \frac{7}{3} n^3 + \frac{3}{2} n^2 + \frac{1}{6} n \\
    & = &   \frac{n (2n + 1) (7n + 1)}{6}
\end{eqnarray*}
}

\problempart
\[
\prod_{i=1}^{n} 3^{4i + 5}
\]

\solution {

This product can be reduced to an easy sum by taking a
logarithm.

\begin{eqnarray*}
\prod_{i=1}^{n} 3^{4i + 5}
    & = &   3^{\log_3\left( \prod_{i=1}^{n} 3^{4i + 5} \right)} \\
    & = &   3^{\sum_{i=1}^n 4i+5} \\
    & = &   3^{2n(n+1) + 5n}
\end{eqnarray*}
}
%\fi

\problempart

\[
\sum_{j=1}^n \sum_{i=0}^{\infty} j^{2/3} \cdot \left(1 - \frac{1}{2 j^{1/3}}\right)^i
\]

\solution {

This fearsome-looking sum is a paper tiger; we just apply
the formula for the sum of a geometric series followed by the formula
for the sum of an arithmetic series.

\begin{eqnarray*}
\sum_{j=1}^n \sum_{i=0}^{\infty} j^{2/3} \cdot \left(1 - \frac{1}{2 j^{1/3}}\right)^i
    & = &   \sum_{j=1}^n j^{2/3} \cdot \frac{1}{1 - \left(1 - \frac{1}{2 j^{1/3}}\right)} \\
    & = &   \sum_{j=1}^n 2j \\
    & = &   n (n+1)
\end{eqnarray*}
}
\iffalse

\problempart

\[
\prod_{i=2}^{n} \left(1 - \frac{1}{i^2}\right)
\]

\solution { 

We give two solutions.  First, evaluating a few terms
suggests that the product is equal to

\[
\frac{n+1}{2n}.
\]

We could verify this by induction.  The calculation needed for the
inductive step is shown below.

\begin{eqnarray*}
\prod_{i=2}^{n+1} \left(1 - \frac{1}{i^2}\right)
    & = &   \left(1 - \frac{1}{(n+1)^2}\right) \cdot
        \prod_{i=2}^{n} \left(1 - \frac{1}{i^2}\right) \\
    & = &   \left(1 - \frac{1}{(n+1)^2}\right) \cdot
        \frac{n+1}{2n} \\
    & = &   \frac{(n+1)+1}{2(n+1)}
\end{eqnarray*}

As an alternative approach, we might observe that this is a
``telescoping product''.

\begin{eqnarray*}
\prod_{i=2}^{n} \left(1 - \frac{1}{i^2}\right)
    & = & \prod_{i=2}^{n} \frac{(i-1)(i+1)}{i^2} \\
    & = & \frac{1 \cdot 3}{2 \cdot 2}
        \cdot \frac{2 \cdot 4}{3 \cdot 3}
        \cdot \frac{3 \cdot 5}{4 \cdot 4} \cdots
        \frac{(n-1) \cdot (n+1)}{n \cdot n} \\
    & = &   \frac{1}{2} \cdot {n+1}{n}
\end{eqnarray*}
}
\fi

\end{problemparts}

\end{examproblem}
\fi

