\documentclass[oneside,12pt]{article}   
\usepackage{latex-macros/course}
\setlength{\topmargin}{0.5in}
\setlength{\headsep}{1cm}
%\showsolutions             
%\hidesolutions             

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% exampreamble %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\renewcommand{\exampreamble}{
  \textbf{Circle the name of your Tutorial Instructor}:
  \begin{center}
  \renewcommand{\arraystretch}{1.5}
  \begin{tabular}{llll}
  Ashish    & Carole   & Christos & Eric \\
  George    & Jack     & Nick     & Tina   
  \end{tabular}
  \end{center}
  \begin{itemize}

  \item This quiz is \textbf{closed book}.  There is an Appendix that
  repeats some key definitions.

  \item 
  There are five (5) problems totaling 100 points.  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{3}                      


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Combinatorics %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}[20]
Four (distinguishable) children approach you on Halloween, requesting candy.
You have 10 pieces of candy to distribute among them, and you don't
want to keep any candy for yourself. Determine how many different ways you
can distribute the 10 pieces under the following conditions. \emph{You may
specify your answer in terms of binomial coefficients.}

\begin{problemparts}

%%%%%%%%
\problempart[6] 
All the pieces are the same (Reese's Peanut Butter Cups\texttrademark).

\solution[\vspace*{3.5cm}]{ This is an indistinguishable balls into
distinguishable urns problem. The candy pieces are the balls and the
children are the urns. Or, in the "stars and bars" forumulation, the
10 stars are the candy pieces and the $4-1$ bars are the separators
between the children.

$$
{10+4-1 \choose 10} = {13 \choose 10} = \frac{13!}{3! \cdot 10!} = 286
$$
}

%%%%%%%%
\problempart[6] 
All 10 pieces of candy are different. 
\solution[\vspace*{3.5cm}]{
$$
4^{10}
$$
}

%%%%%%%%
\problempart[8] 5 pieces are Reese's \texttrademark and the other
5 are Nestl\'{e}'s Crunch\texttrademark.

\solution[\vspace*{5cm}]{ We count the number ways to distribute the
Peanut-Butter cups to children, multiplied by the number of ways to
distribute the Crunch bars.
$$
{5+4-1 \choose 5}\cdot {5+4-1 \choose 5} = {8 \choose 5}^2 =
\left(\frac{8!}{3!5!}\right)^2 = 3136
$$
}

\iffalse
%%%%%%%%
\problempart[6] 
All the pieces are the same, but no child gets more than 4 pieces.

\solution[\vspace*{2cm}]{
We use the formula for 10-combinations of 4 elements with
repetition with each element occuring fewer than 5 times, and get:

$$
{13 \choose 3} - {4 \choose 1}{8 \choose 3} + {4 \choose 2}{3
  \choose 3} = 68
$$
}
\fi
\end{problemparts}
\end{problem}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Pigeonhole principle %%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\begin{problem}[20]
We want to use the generalized pigeonhole principle to prove the
following statement:
\begin{quote}
Among any set of 150 natural numbers, there must be three numbers, 
$a$, $b$, and $c$, such that all of the pairwise differences, 
$(a-b)$, $(a-c)$, $(b-c)$, are multiples of 70.
\end{quote}

\begin{problemparts}
\problempart[3]
What are the pigeons? 
 \solution[\vspace*{2cm}]{The 150 numbers}

\problempart[3]
What are the holes? 
\solution[\vspace*{2cm}]{the set of numbers $\{ 0, \ldots , 69\}$ }

\problempart[3] How will the pigeons be placed in holes? In other words, what
is the function mapping the pigeons to the holes?

\solution[\vspace*{2cm}]{By taking their value mod 70}

\problempart[11]
Carefully prove the statement using the pigeonhole principle.

\solution[\vspace*{6cm}]{ With the pigeons as the 150 numbers, and the
holes as the set of natural numbers mod 70, we see that there is some
hole with $ \ceil{\frac{150}{70}} = 3$ pigeons, that is, three numbers
$a,b,c$ that are equivalent modulo $70$. Then their differences are
equivalent to $0$ modulo $70$, therefore the differences are all
divisible by 70.}

\end{problemparts}

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% False Counting, Combinatorics %%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage
% TOPICS: False Counting, Combinations
\begin{problem}[15]
The Research division of an Electronics Company has 22 regular
employees: 14 MIT graduates (who do the actual research) and 8 Harvard
graduates (who mostly help write the papers at the end). 

To his dismay, Dilbert, the Head of the team, was told by the
company Boss that he must dispatch 6 of these 22 employees to the 
Development division.

To be fair, Dilbert decides he should include \emph{at least} one MIT
graduate in that team of 6. This leads to a lot of possible teams, and
Dilbert decides he'd better count how many.

\begin{quote}
%lets the inline combinations breath
\renewcommand{\baselinestretch}{1.22}\normalsize
(i) Since the team must have at least one MIT graduate, there are
14 ways to select this MIT graduate. This leaves $13+8=21$ people from
which to select the remaining 5 team members, and there are ${21
\choose 5}$ ways to choose those 5 people. Hence there are $14
\cdot {21 \choose 5} = 284886$ teams with at least one MIT graduate.
\end{quote}

To verify his answer, Dilbert decides to count again in a different way.

\begin{quote}
\renewcommand{\baselinestretch}{1.22}\normalsize 
%lets the inline combinations breath 
(ii) There are ${22 \choose 6}$ different possible teams, and ${8
\choose 6}$ teams of just Harvard graduates. So there are ${22
\choose 6} - {8 \choose 6} = 74585$ different possibilities for
teams with at least one MIT graduate.
\end{quote}

Now Dilbert is worried...

\begin{problemparts}

\problempart[5] \label{incorrect}Which count is \emph{incorrect}? (circle one)

\hspace{.5in} (i) only
\hspace{.5in} (ii) only
\hspace{.5in} both  

\solution{(i) only}

\problempart[10] Carefully explain what is wrong with the incorrect
count(s) you indicated in part (\ref{incorrect})

\solution{The first count overcounts the number of teams with
MIT graduates. Consider a team with MIT graduates, Alyssa and Ben on it. This
team is counted twice, once when Alyssa is selected as the first
MIT graduate and a second time when Ben is selected as the first MIT graduate.
Similarly, teams with three or more MIT graduates are overcounted.}

\end{problemparts}
\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Counting Functions/Relations %%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\begin{problem}[20]~~

For each of the following counting problems, choose the formula which
correctly expresses the answer, and write its number in the box.
\newcommand{\answerbox}{ \hspace{1cm}\framebox[1cm]{\strut}}

\begin{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\parbox{5.5in}{
\problempart[4] The number of functions from a set $A$ of size $n$ to a set $B$
of size $m$.\label{func}} 
\answerbox

\solution[\vspace{1cm}]{
%put solutions here
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\parbox{5.5in}{
\problempart[4] \label{inject} The number of \emph{injective}
functions\footnotemark\ from a set $A$ of size $n$ to a set $B$ of
size $m$ (where $m \geq n$).  } 
\answerbox

\footnotetext{$f(x)$ is \emph{injective} if whenever $a \neq b$, $f(a) \neq f(b)$. In other words, $f(a) = f (b) \implies a = b$}

\solution[\vspace{1cm}]{
%put solutions here
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\parbox{5.5in}{
\problempart[4] The number of undirected graphs with exactly $n$
vertices. Self-loops are not allowed.\label{undir}} 
\answerbox

\solution[\vspace{1cm}]{
%put solutions here
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\parbox{5.5in}{
\problempart[4] The number of undirected graphs with exactly $n$ vertices
and exactly $m$ edges. Self-loops are not allowed. \label{undir-exactly}
%(where $m \leq \binom {n}{2}$)
} 
\answerbox

\solution[\vspace{1cm}]{
%put solutions here
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\parbox{5.5in}{
\problempart[4] \label{icecream}
The number of different\footnotemark\ ice cream cones 
with exactly $m$ scoops when $n$ different flavors are available. 
%($m$ may be larger than $n$).
} 
\answerbox
\footnotetext{order of scoops on the cone doesn't matter}
\solution[\vspace{1cm}]{
%put solutions here
}

\end{problemparts}

\textbf{Formula Choices}

\begin{enumerate}
\begin{minipage}[b][4cm][b]{0.75in}
	\item $2^{mn}$ 
	\item $ m^n$   
	\item $ n^m$ 
	\item $\binom{m+n-1}{m}$ 
	\item $\binom{m+n-1}{n}$   
\end{minipage}\hspace{1in}
\begin{minipage}[b][4cm][b]{0.75in}
	\item $\binom{m}{n}$   
	\item $\binom{n}{m} $ 
	\item $\binom{m}{n} \cdot n! $ 
	\item $\binom{n}{m}\cdot m!$   
	\item $2^{n^2}$   
\end{minipage}\hspace{1in}
\begin{minipage}[b][4cm][c]{3in}
	\item $2^{\binom{n}{2}}$   
	\item $\binom{\binom{n}{2}}{m}$  
	\item None of the above 
\end{minipage}
\end{enumerate}

\solution{
\begin{center}
\begin{tabular}[h]{|c|c|}
\hline 
  Formula & Parts \\\hline	
  $\displaystyle2^{mn}$ & \\ \hline
  $\displaystyle m^n$ &\ref{func} \\ \hline
  $\displaystyle n^m$ & \\ \hline
  $\displaystyle\binom{m+n-1}{m}$ &\ref{icecream} \\ \hline
  $\displaystyle\binom{m+n-1}{n}$ & \\ \hline
  $\displaystyle\binom{m}{n}$ & \\ \hline
  $\displaystyle\binom{n}{m} $ & \\ \hline
  $\displaystyle\binom{m}{n}n! $ &\ref{inject} \\ \hline
  $\displaystyle\binom{n}{m}m!$ & \\ \hline
  $\displaystyle2^{n^2}$ & \\ \hline
  $\displaystyle2^{\binom{n}{2}}$ &\ref{undir} \\ \hline
  $\displaystyle\binom{\binom{n}{2}}{m}$ &\ref{undir-exactly} \\ \hline
	None of the above & \\ \hline
\end{tabular}
\end{center}
}

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Conditional probability %%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\begin{problem}[25]
A bag contains $1000$ nickels, of which $999$ are regular (fair)
nickels and $1$ is a two-headed nickel. Experiment X$(k)$ consists of
pulling a coin out of the bag at random, flipping it $k$ times and
then putting it back.
\begin{problemparts}
\problempart[9]
Ben Bitdiddle has volunteered to perform X$(10)$.
\begin{itemize}
\item Let $a$ be the probability that Ben gets $10$ heads given
that he pulled out the two-headed nickel. What is the value of $a$?

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


\item Let $b$ be the probability that Ben gets $10$ heads given that he
pulled out a regular nickel. What is the value of $b$?

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

\item Let $c$ be the probability that Ben gets 10 heads 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}{1000}}a+\paren{\frac{999}{1000}}b
\end{eqnarray*}
}

\end{itemize}

\problempart[8] Ben has just performed X$(10)$ and ended up getting
$10$ heads! Let $d$ be the probability that he pulled out the
two-headed coin, given that he flipped 10 heads. 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 Ben pulled out the two-headed coin. Let $B$ be
the event that Ben got $10$ heads. Then:
\[
d~=~Pr(A|B)~ =~ \frac{Pr(A)}{Pr(B)}Pr(B|A)~ =~ \frac{1/1000}{c}\cdot 1~ =~ \frac{1}{1000c}
\]
}

\problempart[8] Another subject, Alyssa, performs X$(10)$, and ends up
getting $10$ heads 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). 

\solution[\vspace*{3cm}]{ 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 2^{-10}
\end{eqnarray*}
}
\end{problemparts}
\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Appendix %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\appendix
\setcounter{secnumdepth}{1}
\section{Appendix}

\subsection{Combinatorics}

\iffalse
\subsubsection{Summation}
\begin{eqnarray*}
\sum_{i=0}^{n} i^2 & = & \frac{n(n+1)(2n+1)}{6}\\
\sum_{i=0}^{n} x^i & = & \frac{1- x^{n+1}}{1 - x}\\
\sum_{i=0}^{\infty} x^i & = & \frac{1}{1-x}\\
\sum_{i=1}^{n} i x^i & = & \frac{x - (n+1)x^{n+1} + n x^{n+2}}{(1 - x)^2}\\
\sum_{i=1}^{\infty} i x^i & = & \frac{x}{(1-x)^2}\\
\sum_{i=1}^\infty{i^2x^i} & = & \frac{x(1+x)}{(1-x)^3}\\
e^x & = & 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots\\
1 + x & \leq & e^x\\
H_n & \eqdef & \sum_{i=1}^n \frac{1}{i} \quad\quad \text{(Harmonic Numbers)}\\
H_n &\sim& \ln n
\end{eqnarray*}
\fi

\subsubsection{Counting}
Given a set of $n$ elements:
\begin{itemize}
\item number of $r$-permutations without repetition:
\[P(n, r) \eqdef n (n-1) \ldots (n-r+1) = \frac{n!}{(n-r)!}\]

\item $r$-combinations without repetition:
\[C(n,r) \eqdef \binom{n}{r} = \frac{n!}{(n-r)! \ r!}\]

\item $r$-permutations with unlimited repetition ($r$ distinct balls, $n$ distinct
bins):
\[
n^r
\]

\item $r$-combinations with repetition ($r$ identical balls, $n$ distinct
bins):
\[\binom{n+r-1}{r}\]

\item permutations with limited repetition:
\[\binom{n}{r_1, r_2, \ldots, r_k} \eqdef\frac{n!}{r_1!\ r_2! \ldots r_k!}\]
where $r_1 + r_2 + \cdots + r_k = n$.
\end{itemize}

\subsubsection{Binomial Identity}
\[\binom{n}{m} = \binom{n}{n-m}\]

\subsubsection{Multinomial Theorem}
\[(x_1 + x_2 + \ldots + x_k)^n =
	\sum_{r_1 + r_2 + \ldots + r_k = n} \binom{n}{r_1, r_2, \ldots, r_k}
	x^{r_1} x^{r_2} \ldots x^{r_k}\]

\subsubsection{Inclusion-Exclusion}
\[|A_1 \cup \ldots \cup A_n| = \sum_{k=1}^n
(-1)^{k+1} \left( \sum_{S \subseteq \{1,\ldots,n\}, |S| = k} | \bigcap_{i
\in S} A_i |\right)\]

\iffalse
\subsubsection{Stirling's Approximation}
\[
n! = \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n e^{a_n}
\]
where
\[
1/(12n+1) \leq a_n \leq 1/(12n).
\]
\fi

\subsection{Events}

\begin{align}
\pr{\lgunion_{n \in \naturals} A_n} & = \sum_{n \in \naturals} \pr{A_n}
\quad \mbox{for pairwise disjoint $A_n$} \tag{Sum Rule}\\
\pr{A-B}  & =  \pr{A} - \pr{A \intersect B} \tag{Difference Rule} \\
\pr{\bar{B}}  & =  1 - \pr{B} \label{1-b} \tag{Complement Rule}\\
\pr{A \union B}  & = \pr{A} + \pr{B} - \pr{A \intersect B} \tag{Inclusion-Exclusion}\\
\pr{A \union B} & \le \pr{A}+ \pr{B} \tag{Boole's inequality} \\
\pr{A} & \le \pr{B}, \quad\text{ for } A \subseteq B \tag{Monotonicity}\\
\pr{A \intersect B} & \le  \pr{A}, \notag\\
\pr{A} & \le \pr{A \union B} \notag\\
\prcond{A}{B} {\pr{B}}  & =  \pr{A \intersect B}\tag{Product Rule}\\
\prcond{A}{B} & = \frac{\prcond{B}{A}\pr{A}}{\pr{B}} \tag{Bayes Rule}
\end{align}

\begin{lemma*}[Law of Total Probability]
Let $B_0, B_1, \ldots$ be disjoint events whose union is the
entire sample space.  Then for all events $A$,
\begin{align}
\pr{A} &= \sum_{i \in \naturals} \pr{A \cap B_i}, \notag\\
\pr{A} &= \sum_{i \in \naturals} \pr{A | B_i}\pr{B_i}. \tag{conditional form}
\end{align}
\end{lemma*}

\subsection{Independence}
\begin{definition*}
Events $A$ and $B$ are \emph{independent} iff
\[
\pr{A \intersect B} = \pr{A}\pr{B}.
\]

Events $A_0,A_1,A_2,\dots$ are \emph{mutually independent} iff for all
subsets $J \subseteq \naturals$,
\[
\pr{\lgintersect_{i\in J} A_i} = \prod_{i \in J} \pr{A_i}.
\]

Events $A_0,A_1,A_2,\dots$ are \emph{$k$-wise independent} iff $\set{A_i
\suchthat i\in J}$ are mutually independent for all subsets $J \subset
\naturals$ with $\card{J} = k$.
\end{definition*}

\end{document}



