\documentclass[12pt]{article}
\input{macros-course}

\makeatletter
\renewcommand\theenumi{\@alph\c@enumi}
\renewcommand\theenumii{\@roman\c@enumii}

\renewcommand\labelenumi{\theenumi)}
\renewcommand\labelenumii{\theenumii)}

\def\ps@myheadings{%
    \let\@oddfoot\@empty\let\@evenfoot\@empty
    \def\@evenhead{\thepage\hfil\slshape\leftmark}%
    \def\@oddhead{\rlap{\slshape\rightmark}\hfil\thepage\hfil \llap{Name:\brule{2in}}}%
    \let\@mkboth\@gobbletwo
    \let\sectionmark\@gobble
    \let\subsectionmark\@gobble
    }

\makeatother

\askaboutsolutions

\begin{document}

%% Quiz 2

\ifshowsolutions
  \qsol{3}{November 16, 2001}{\stamp}
\else
  \quiz{3}{November 16, 2001}{\stamp}

\textbf{Your Name}:\ \mbox{}\hrulefill\mbox{}\par

\textbf{Circle the name of your Tutorial Instructor}:\\
\begin{center}
\begin{tabular}{l@{\hskip 3em}l@{\hskip 3em}l@{\hskip 3em}l}
Yu-Han & Christos & Nikos & Ashish \\
\ &&& \\
Thien-Loc & Jaime & Tina & Tong
\end{tabular}
\end{center}

%\noindent Write the hour at which your Thursday tutorial begins \brule{3em}.

\medskip

\begin{closeitemize}
\item This quiz is \textbf{closed book}.  \iffalse There is an Appendix
that includes some standard definitions. The first occurrence of an
item defined in the appendix appears in \textbf{boldface}.\fi

\item There are five (5) problems each worth 20 points.

\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 \remove{Show your work, as partial credit will be given.}
\textbf{Be neat and write legibly}.  You will be graded not only on the
correctness of your answer, but also on how clearly you present it.

\item GOOD LUCK!
\end{closeitemize}

\bigskip

\hrule
\smallskip
\centerline{\textbf{DO NOT WRITE BELOW THIS LINE}}
\smallskip
\hrule

\medskip\begin{center}
\renewcommand{\arraystretch}{.3}
\begin{tabular}{|c|c|c|}
\hline & &\\
Problem & Grade & Grader\\
\hline \hline  & &\\
1 &   & \\ & & \\ \hline  & &\\
2 &   & \\ & & \\ \hline  & &\\
3 &   & \\ & & \\ \hline  & &\\
4 &   & \\ & & \\ \hline  & &\\
5 &   & \\ & &\\
\hline \hline  & &\\
Total &  & \\
& &\\
\hline
\end{tabular}
\end{center}

\newpage
\fi

\iffalse

\begin{verbatim}

%% Quiz 3:
%%-----------
%% Subjects:
%% Summations (series, closed forms, stirling, asymptotic)
%% Counting (sum and product rules, incl-excl, trees, bijections, pigeonhole)
%% (permutations, combinations, binomial theorem and identities, repetitions)
%% Probability (basics, combination of events, conditional)

\end{verbatim}
\fi

\ifshowsolutions
 {}
\else
\newpage
\fi

\begin{problems}

\problem %Annuities

Suppose that you plan to purchase an annuity that pays you $m$ dollars per
year for $n$ years, starting $d$ years from now.  Suppose the interest
rate you could earn from a bank is such that \$$r$ deposited today will grow
to be $\$1$ in one year, \eg if the interest rate is 5\%, then $r =
1/1.05$.  Assume this rate will remain fixed forever.  Find a closed-form
formula in $m,n,d$ and $r$ for the current value of this annuity.

\ifshowsolutions
 {}
\else
\vspace{2in}
\fi

\solnospace{
\begin{eqnarray*}
\text{Current price of the annuity}
& = & \sum_{i=d}^{n+d-1} mr^i\\
& = & \sum_{i=0}^{n+d -1}mr^i - \sum_{i=0}^{d-1}mr^i\\
& = & \frac{m ((r^{n+d} -1) - (r^{d}-1))}{r-1}\\
& = & \frac{mr^d(1- r^n)}{1-r}
\end{eqnarray*}
}

\iffalse

\ppart Find a closed-form formula for the same annuity if instead of
$n$ years, it pays forever.

\ifshowsolutions
 {}
\else
\vspace{1in}
\fi

\solnospace{$\frac{mr^d}{1-r}$}

\eparts
\fi


%------------------------------------------------------------------%
% source: substantially revised from Fall 1998 Midterm

\problem

\bparts

\ppart Write closed form formulas which may involve factorials and
binomial coefficients for the following four functions:

\begin{itemize}

\item $G(n)\eqdef $ the number of directed simple graphs with vertices
$\set{ 1, 2, \dots, n }$ (self-loops permitted).

\brule{1in}
\solnospace{$2^{n^2}$.  There are $n^2$ possible directed edges, each of
which may or may not be in a graph.}

\item $U(n) \eqdef$ the number of undirected simple graphs with vertices
$\set{ 1, 2, \dots, n }$ (self-loops NOT permitted).

\brule{1in}
\solnospace{$2^{\binom{n}{2}}$.  There are $\dbinom{n}{2}$ possible
undirected edges between distinct vertices, and each edge may or may not
be in a graph.}

\item $M(n) \eqdef$ the number of mappings from $\set{ 1, 2, \dots, n
}$ to $\set{ 1, 2, \dots, 2n }$.

\brule{1in} \solnospace{$(2n)^n$.  For each of the $n$ arguments of a
mapping, there are $2n$ possible values.
  
  Note: We used the word ``mapping'' to mean a \emph{function} from one
  set to another, \ie an assignment of exactly one element of the first
  set, $\set{1,\dots,n}$, to an element of the second set.  However, some
  of you took mapping to mean any relation between the two sets.  In this
  case, the number of relations between $\set{ 1, 2, \dots, n }$ and
  $\set{ 1, 2, \dots, 2n }$ is $(2^{2n})^n = 2^{2n^2}$; we awarded full
  credit for this answer also.}

\item $B(n) \eqdef$ the number of \emph{injections} from $\set{ 1, 2,
\dots, n }$ to $\set{ 1, 2, \dots, 2n }$.

\brule{1in} \solnospace{$P(2n,n) = \cfrac{2n!}{n!}$.}

\end{itemize}

\ppart Order the functions $G,U,M,B$ above so that each function is O() of
the next function.  Also indicate whether the $\Theta()$ relationship
holds between each successive pair of functions.  No proofs are required.


\ifshowsolutions
 {}
\else
\vspace{1in}
\fi

\solnospace{The order is $B, M, U, G$, and each is o() of the next, and
therefore is O() but not $\Theta()$ of the next.

\[
B(n) = \frac{2n!}{n!} \sim \frac{\sqrt{2\pi 2n}(\frac{2n}{e})^{2n}}{\sqrt{2\pi
n}(\frac{n}{e})^n} = \sqrt{2} \frac{(2n)^{2n}}{(en)^n} = \sqrt{2}
(\frac{4}{e})^n n^n = o(2^n) n^n = o((2n)^n).
\]

Note that Stirling's formula is not really needed here, since we can
also reason in a simple way as follows:
\begin{eqnarray*}
\frac{2n!}{n!} &  =  & 2n(2n-1)\cdots\ceil{(3/2)n}(\ceil{(3/2)}n-1)\cdots
(n+1)\\
& \le & (2n)^{\floor{n/2}}((3/2)n)^{\ceil{n/2}}\\
& = & (2n)^{n/2}\cdot o((2n)^{n/2})\\
& = & o((2n)^n).
\end{eqnarray*}
\[
M(n) = (2n)^n = 2^n n^n = 2^n2^{n\log n}=2^{n(1+\log n)} = 2^{o(n^2)} =
o(2^{\binom{n}{2}}).
\]
\[
U(n) = 2^{\binom{n}{2}} \le 2^{n^2/2} = (\sqrt{2})^{n^2} = o(2^{n^2}),
\]
so
\[
U(n) = o(G(n)).
\]

In grading this part of the problem, we only considered your answers from
part (a).  So if you answered part (a) with incorrect formulas but were
still able to order these formulas correctly, you were awarded full credit
for part (b).  Conversely, if your answer to (b) was inconsistent with
your answer to (a), you did not receive credit even if you happened to
come up with the ``correct'' sequence $B, M, U, G$.

If you took ``mapping'' to mean ``relation'' as described in the part
(a) solution for $M(n)$, then the correct order is $B, U, G, M$.  
}

\eparts

\problem  %pigeon hole, perms and combs

We know how the ``Magic'' trick works in which an Assistant reads
four cards from a five card hand and the Magician predicts the fifth card.
We also know the trick cannot be made to work if the Assistant only
shows three cards from a four card hand, because there are fewer sequences
of three out of 52 cards than there are 4-card hands out of 52 cards.

A basic result in matching theory called \emph{Hall's Theorem} implies
that, in general, the trick is possible using $h$-card hands chosen from
an $n$-card deck, with the Assistant reading $r$ of the $h$ cards as long
as the following condition holds:
\begin{quotation}\noindent
for \emph{every subset} of the $n$ cards in the deck, the number of
$h$-card \emph{hands} from that subset is at most as large as the number
of $r$-card \emph{sequences} from that subset.
\end{quotation}
Given Hall's Theorem (which is not at all obvious by the way),
what is the largest size deck for which our trick of reading four cards
from a 5-card hand remains possible?

\ifshowsolutions
 {}
\else
\vspace{0.5in}
\fi

\brule{1in}

\solnospace{Need
\[
\binom{k}{5} \le (k)_4
\]
for all $k \le n$.  That is,
\begin{eqnarray*}
\frac{k!}{(k-5)!5!} &\le& k(k-1)(k-2)(k-3)\\
\frac{k(k-1)(k-2)(k-3)(k-4)}{5!} &\le& k(k-1)(k-2)(k-3)\\
\frac{(k-4)}{5!} &\le& 1\\
k &\le& 124.
\end{eqnarray*}
So $n = 124$ is the largest size deck for which the trick is possible.
}

\ifshowsolutions
 {}
\else
\vspace{3in}
\fi

\problem

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?

\ifshowsolutions
 {}
\else
\vspace{0.5in}
\fi

\brule{1in}

\ifshowsolutions
 {}
\else
\vspace{2.5in}
\fi

\solnospace{$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.
}

\iffalse

\problem Consider the 11 letter word \emph{albertmeyer}.  For each of
the following questions, it is ok to express your answer as a number
\emph{or} as a simple expression involving factorials.

\bparts

\ppart How many different sequences of these letters are there?

\ifshowsolutions
 {}
\else
\vspace{0.5in}
\fi

\brule{1.5in}
\solnospace{$\dbinom{11}{3,2,1,1,1,1,1,1} = \cfrac{11!}{12}$}

\ifshowsolutions
 {}
\else
\vspace{0.5in}
\fi

\ppart How many different sequences of these letters are there that
contain the word \emph{eye}?

\ifshowsolutions
 {}
\else
\vspace{0.5in}
\fi

\brule{1.5in}
\solnospace{$\dbinom{11-3+1}{2,1,1,1,1,1,1,1,1,1} = \cfrac{9!}{2}$}

\ifshowsolutions
 {}
\else
\vspace{0.5in}
\fi

\ppart How many are there that do \emph{not} contain either of the words
\emph{eye} or \emph{tram}?

\ifshowsolutions
 {}
\else
\vspace{1.5in}
\fi

\brule{4in}

\solnospace{
\begin{eqnarray*}
\mbox{Arrangements with eye: use} \set{a,l,b, e,r,t,m, eye, r} & = & \cfrac{9!}{2}\\
\mbox{Arrangements with tram: use} \set{tram,l,b,e, e,y,e, r} & = &
\dbinom{8}{3,1,1,1,1,1} = \cfrac{8!}{3!}\\
\mbox{Arrangements with tram and eye: use} \set{tram,l,b,e,eye,r} & = & 6!\\
\mbox{Arrangements with neither tram nor eye}
      & = & \cfrac{11!}{12} - \cfrac{9!}{2} - \cfrac{8!}{3!} + 6!.
\end{eqnarray*}
}

\eparts

\fi

\problem You are organizing a neighborhood census and instruct
your census takers to knock on doors and note the sex of any child that
answers the knock.  Assume that there are two children in a household and
that girls and boys are equally likely to be children and to open the
door.

A sample space for this experiment has outcomes that are triples whose
first element is either \texttt{B} or \texttt{G} for the sex of the elder
child, likewise for the second element and the sex of the younger child,
and whose third coordinate is \texttt{E} or \texttt{Y} indicating whether
the \emph{e}lder child or \emph{y}ounger child opened the door.  For
example, $(\mathtt{B},\mathtt{G},\mathtt{Y})$ is the outcome that the elder
child is a boy, the younger child is a girl, and the girl opened the door.

\problempart Let \emph{T} be the event that the household has two girls,
and \emph{O} be the event that a girl opened the door.  List the outcomes
in
\begin{itemize}

\item \emph{T}: \brule{5in}  \solnospace{GGE,GGY}
\item \emph{O}: \brule{5in} \solnospace{GGE,GGY,GBE,BGY}

\end{itemize}

\ppart What is the probability $\prcond{T}{O}$, that both children are
girls, given that a girl opened the door?
\brule{1in} \solnospace{1/2}

\ifshowsolutions
 {}
\else
\vspace{1.0in}
\fi


\problempart Where is the mistake in the following argument?

\begin{quotation}
{\em
\noindent If a girl opens the door, then we know that there is at least
one girl in the household.  The probability that there is at least one
girl is
\begin{equation}
1 - \prob{\text{both children are boys}} = 1 - (1/2 \times 1/2) = 3/4.
\end{equation}
So,
\begin{eqnarray}
\lefteqn{\prcond{T}{\text{there is at least one girl in the household}}}\\
& = & \frac{\prob{T \intersect \text{there is at least one girl in the household}}}
{\pr{\text{there is at least one girl in the household}}}\\
& = & \frac{\prob{T}}{\pr{\text{there is at least one girl in the household}}}\\
& = & (1/4) / (3/4) = 1/3.
\end{eqnarray}
Therefore, given that a girl opened the door, the probability that there
are two girls in the household is \textup{1/3}.
}
\end{quotation}

\ifshowsolutions
 {}
\else
\vspace{4in}
\fi

\solnospace{The argument is a correct proof that 
\[
\prcond{T}{\text{there is at least one girl in the household}} = 1/3.
\]
The problem is that the event, $H$, that the household has at least one girl,
namely,
\[
H \eqdef \set{\mathtt{GGE,GGY,GBE,GBY,BGE,BGY}},
\]
is not equal to the event, \emph{O}, that a girl opens the door.  These
two events differ:
\[
H-O = \set{\mathtt{BGE,GBY}},
\]
and their probabilities are different.  So the fallacy is in the final
conclusion where the value of $\prcond{T}{\text{there is at least one girl
in the household}}$ is taken to be the same as the value $\prcond{T}{O}$.
Actually, $\prcond{T}{O} = 1/2$.

\iffalse
For having children, each case GG, GB, BG and BB is equally
likely.  However given GG, the probability that a girl opens the door
is 1.  Given the GB or BG the probability is 1/2.  Given BB the
probability that a girl opens the door is 0.  Therefore the probability
that a girl opens the door is not the same for all four cases of
children pairs.  Since the four children pairs are disjoint we can
simply add up the conditional probabilities that a girl opens for each
pair (by the total probability rule).

Note that GB and BG are distinct cases. It is similar to saying that
flipping HT is different from flipping TH for after all what is having
kids but flipping a coin.
\fi
}

\end{problems}

\end{document}


\iffalse

\newpage
%----------------------------------------------------------------------------%

% source: Fall 2000 Quiz 2
\problem {\bf Simple Summations (arithmetic and Geometric Series)}
Find the closed form for each of the expressions listed below.  Give
your answer in simplified form.

\problempart $\sum_{i=x}^{y} 2i+1 $

\solnospace{There are two ways of doing this problem.  In the first,
we re-form the sum so the lower limit is 0 instead of $x$ and apply
the arithmetic sum formula.

$$\sum_{i=x}^y 2i+1 = \sum_{i=0}^{y-x} 2(i+x)+1$$
$$= \sum_{i=0}^{y-x} 2i + 2x+1$$
$$= (y-x+1)(2x+1) + 2 \sum_{i=0}^{y-x} i $$
$$= (y-x+1)(2x+1) + 2 \frac{(y-x)(y-x+1)}{2} $$
$$= (y-x+1)(2x+1 + y-x) = (y-x+1)(y+x+1) = ((y+1)-x)((y+1)+x) $$
$$= (y+1)^2 - x^2.$$


In the second, we express this sum as the difference of two summations,
one involving only $y$ and one involving only $x$.  

$$\sum_{i=x}^{y} 2i+1 = \sum_{i=0}^{y} 2i + 1 - (\sum_{0=1}^{x-1} 2i +
1).$$

Now, since 

$$\sum_{i=0}^n 2i+1 = n+1 + 2\frac{n(n+1)}{2} = n+1 + n(n+1) = n^2 +
2n+1 = (n+1)^2,$$

we can evaluate this to

$$(y+1)^2 - x^2.$$
}

\problempart $\sum_{i=0}^{\infty} \sum_{j=1}^n \frac{1}{2^i}$

\solnospace{

The inner sum, 

$$ \sum_{j=1}^n \frac{1}{2^i} $$

is very simple since $j$ is not involved in the inner term.  The
closed form for this is simply

$$ \frac{n}{2^i} $$.

Since $n$ is a constant, we can take it out, and evaluate a simple
infinite geometric sum to get $\sum_{i=0}^{\infty} \sum_{j = 1}^n
\frac{1}{2^i} = 2n$
}



\begin{eqnarray}
\lefteqn{\prcond{T}{\text{a girl opens the door}}}\\
 & = & \prcond{T}{\text{there is at least one girl in the household}}\label{fallacy}\\
& = & \frac{\prob{T \intersect \text{there is at least one girl in the household}}}
{\pr{\text{there is at least one girl in the household}}}\\
& = & \frac{\prob{T}}
{\pr{\text{there is at least one girl in the household}}}\\
& = & (1/4) / (3/4) = 1/3.
\end{eqnarray}

\fi
