\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


\renewcommand{\exampreamble}{	% !! renew \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 giving the 
  definitions of some standard operations on relations.
  \item 
  There are four (4) 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}			% !! start the paper



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


\begin{problem}[10]		% !! Define points next to each problem
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.
\end{problem}

\solution{
\begin{align*}
\text{Current price of the annuity}
& = 
\sum_{i=d}^{n-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{align*}
}








\begin{problem}[20]		% !! Define points next to each problem
\begin{problemparts}

\problempart 
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}

\solution{$2^{n^2}$}

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

\solution{$2^{\binom{n}{2}}$}

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

\solution{$(2n)^n$}

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

\solution{$\cfrac{2n!}{n!}$}
\end{itemize}

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

\solution{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)).
$$
}
\end{problemparts}
\end{problem}








\begin{problem}[30]  			% !! Define points next to each problem
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?
\brule{1in}
\end{problem}

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






\begin{problem}[40]		% !! Define points next to each 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?
\brule{1in}
\end{problem}

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







\begin{problem}[50]			% !! Define points next to each problem
You are organizing a neighborhood census and instruct our 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.
\begin{problemparts}

\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}  

\solution{GGE,GGY}

\item 
\emph{O}: \brule{5in} 

\solution{GGE,GGY,GBE,BGY}
\end{itemize}

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

\solution{1/2}

\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}

\solution{
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$.
}
\end{problemparts}
\end{problem}


\end{document}
