\documentclass[12pt,oneside]{article}
\usepackage{light}

%\hidesolutions
\showsolutions

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\generic{Quiz 2}{November 16, 2004}


\begin{center}
\textbf{YOUR NAME: } \underline{\hspace{3in}}
\end{center}

\textbf{Circle the name of your recitation instructor}:

\begin{center}
\begin{tabular}{ccccccccc}
Albert && Claire && Edmond && Florent && Nick
\end{tabular}
\end{center}

\begin{itemize}

\item You may use one $8.5 \times 11$'' sheet with notes in your own
handwriting on both sides, but no other reference materials.
Calculators are not allowed.

\item You may assume all results presented in class.

\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 Be neat and write legibly.  You will be graded not only on the
correctness of your answers, but also on the clarity with which you
express them.

\item The exam ends at 9:30 PM.

\end{itemize}

\centerline{GOOD LUCK!}


\vspace{0.25in}

\begin{center}
{\large
\begin{tabular}{|c|c|c|c|}
\hline
Problem & Points & Grade & Grader \\ \hline \hline
1 & 10 & & \\ \hline
2 & 10 & & \\ \hline
3 & 10 & & \\ \hline
4 & 15 & & \\ \hline
5 & 40 & & \\ \hline
6 & 15 & & \\ \hline
Total & 100 & & \\ \hline 
\end{tabular}
}
\end{center}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\begin{problem}(10 points)
Evaluate the following sum:
%
{\large
\[
\sum_{i=0}^{\infty} \sum_{j=0}^{\infty} 2^{-(i+j)}
\]
}

\solution{
We use the formula for the sum of a geometric series:
%
\begin{align*}
\sum_{i=0}^{\infty} \sum_{j=0}^{\infty} 2^{-(i+j)}
    & = \sum_{i=0}^{\infty} 2^{-i} \cdot
        \left( \sum_{j=0}^{\infty} 2^{-j} \right) \\
    & = \sum_{i=0}^{\infty} 2^{-i} \cdot 2\\
    & = 2 \cdot \sum_{i=0}^{\infty} 2^{-i} \\
    & = 2 \cdot 2 \\
    & = 4 \\
\end{align*}
}

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\newcommand{\mybox}[1]{\quad = \quad
                       \fbox{\rule{0in}{0.15in}{\hspace{0.25in}}}
                       \left(#1\right)}

\begin{problem} (10 points) Circle every symbol on the left that could
correctly appear in the box to its right.  (Thus, for each of the five
parts you may circle zero, one, or both of the symbols.)

{\Large
\begin{align*}
\mathbf{(a)} && \Theta \hspace{0.5in} \omega && \hspace{0.5in}
  10^n & \mybox{n^{10}} \\[0.35in]
\mathbf{(b)} && o \hspace{0.5in} O && \hspace{0.5in}
  \frac{1}{\log n} & \mybox{1} \\[0.35in]
\mathbf{(c)} && \Omega \hspace{0.5in} o && \hspace{0.5in}
  \sqrt{n} & \mybox{(\log n)^5} &  \\[0.35in]
\mathbf{(d)} && O \hspace{0.5in} \Omega && \hspace{0.5in}
  n^2 & \mybox{3 n^2 - 5 n + 7} \\[0.35in]
\mathbf{(e)} && \Theta \hspace{0.5in} O && \hspace{0.5in}
  n! & \mybox{n^n}
\end{align*}
}

\end{problem}

\solution{
Underlined symbols should be circled.
%
{\Large
\[
\begin{array}{cc}
\Theta & \underline{\omega} \\
\underline{o} & \underline{O} \\
\underline{\Omega} & o \\
\underline{O} & \underline{\Omega} \\
\Theta & \underline{O}
\end{array}
\]
}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\begin{problem} (10 points) Caesar conquers an $x$-square-mile region as
follows.

\begin{itemize}

\item If $0 < x \leq 1$, then he conquers the whole region in 1 day.

\item If $x > 1$, then he spends $\log x$ days partitioning the
region into three nonoverlapping parts with sizes $x/6$, $2x/6$, and
$3x/6$.  Then he conquers each part recursively, one at a time.

\end{itemize}

\noindent Let $C(x)$ be the number of days Caesar needs to conquer an
$x$-square-mile region.  Express $C(x)$ with a recurrence equation and
suitable boundary condition.  Note that $x$ is not necessarily an
integer.  \textit{Do not solve the recurrence.}

\solution{
\[
C(x) =
\begin{cases}
1 & \text{if } 0 < x \leq 1 \\
\log x + C\left(\frac{1}{6}x\right) + C\left(\frac{2}{6}x\right) + C\left(\frac{3}{6}x\right) & \text{if } x > 1
\end{cases}
\]
}

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\begin{problem}(15 points) Find a closed-form expression for $T(n)$, which
is defined by the following recurrence:
%
\begin{align*}
T(0) & = 0 \\
T(1) & = 1 \\
T(n) & = 5 T(n-1) - 6 T(n-2) + 6 \qquad \text{for all } n \geq 2
\end{align*}
\end{problem}

\solution{The characteristic equation is $x^2 - 5 x + 6 = 0$, which has roots $x = 2$ and $x = 3$.  Thus, the homogenous solution is:
%
\[
T(n) = A \cdot 2^n + B \cdot 3^n
\]
%
For a particular solution, let's first guess $T(n) = c$:
%
\begin{align*}
c & = 5 c - 6 c + 6 \\
\implies c & = 3
\end{align*}
%
Our guess was correct; $T(n) = 3$ is a particular solution.  Adding
this to the homogenous solution gives the general solution:
%
\[
T(n) = A \cdot 2^n + B \cdot 3^n + 3
\]
%
Substituting $n = 0$ and $n = 1$ gives:
%
\begin{align*}
0 & = A + B + 3 \\
1 & = 2 A + 3 B + 3
\end{align*}
%
Solving this system gives $A = -7$ and $B = 4$.  Therefore:
%
\[
T(n) = -7 \cdot 2^n + 4 \cdot 3^n + 3
\]
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\begin{problem} (40 points) Solve the three counting problems below.  The
answers alone are sufficient, but we can only award partial credit if
you show your work.  You do not need to simplify your answers; you may
leave factorials, binomial coefficients, and arithmetic expressions
unevaluated.

\bparts

\ppart (15 points) How many seven-card poker hands contain three pairs
and no three-of-a-kind or four-of-a-kind?

\solution[\vspace{3in}]{
There is a bijection with sequences specifying:
%
\begin{itemize}
\item The values of the pairs, which can be chosen in $\binom{13}{3}$
ways.
\item The suits of the lowest-value pair, which can be chosen in
$\binom{4}{2}$ ways.
\item The suits of the middle-value pair, which can be chosen in
$\binom{4}{2}$ ways.
\item The suits of the highest-value pair, which can be chosen in
$\binom{4}{2}$ ways.
\item The value of the remaining card, which can be chosen in 10 ways.
\item The suit of the remaining card, which can be chosen in 4 ways.
\end{itemize}
%
Thus, the number of seven-card poker hands containing three pairs and
no three or four-of-a-kind is:
%
\[
\binom{13}{3} \cdot \binom{4}{2}^3 \cdot 10 \cdot 4
\]
%
By the Generalized Product Rule.}


\ppart (10 points) A shelf holds 17 books in a row.  How many ways are
there to choose 4 books so that there are at least two books between
every pair of chosen books?

\solution[\newpage]{There exists a bijection from 11-bit sequences
with exactly four 1's to valid book selections.  Map each zero to a
non-chosen book, each of the first three 1's to a chosen book followed
by two non-chosen books, and the last 1 to a chosen book.  For example,
the 11-bit sequence:
%
\[
(0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1)
\]
%
maps to the book selection:
%
\[
\underbrace{n}_{0}\
\underbrace{n}_{0}\ 
\underbrace{c\ n\ n}_{1}\
\underbrace{n}_{0}\
\underbrace{c\ n\ n}_{1}\
\underbrace{c\ n\ n}_{1}\
\underbrace{n}_{0}\ 
\underbrace{n}_{0}\ 
\underbrace{n}_{0}\ 
\underbrace{n}_{0}\ 
\underbrace{c}_{1}
\]
%
where $c$ denotes a chosen book and $n$ denotes a non-chosen book.
Therefore, the number of valid book selections is $\binom{11}{4}$.}

\ppart (15 points) The working days in the next year can be numbered
1, 2, 3, \ldots, 300.  I'd like to avoid as many as possible.
%
\begin{itemize}
\item On even-numbered days, I'll say I'm sick.
\item On days that are a multiple of 3, I'll say I was stuck in traffic.
\item On days that are a multiple of 5, I'll refuse to come out from under the blankets.
\end{itemize}
%
In total, how many work days will I \textit{avoid} in the coming year?

\solution{Let $D_2$ be the set of even-numbered days, $D_3$
be the days that are a multiple of 3, and $D_5$ be days that are a
multiple of 5.  The set of days I can avoid is $D_2 \cup D_3 \cup
D_5$.  By the Inclusion-Exclusion Rule, the size of this set is:
%
\begin{align*}
\size{D_2 \cup D_3 \cup D_5}
    & = \size{D_2} + \size{D_3} + \size{D_5} \\
    & \quad - \size{D_2 \cap D_3} - \size{D_2 \cap D_5} - \size{D_3 \cap D_5}\\
    & \quad + \size{D_2 \cap D_3 \cap D_5} \\
    & = \frac{300}{2} + \frac{300}{3} + \frac{300}{5}
        - \frac{300}{2 \cdot 3} - \frac{300}{2 \cdot 5} - \frac{300}{3 \cdot 5}
        + \frac{300}{2 \cdot 3 \cdot 5} \\
    & = 220
\end{align*}
}

\eparts

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\begin{problem} (15 points)
Miss McGillicuddy never goes outside without a collection of pets.  In
particular:
%
\begin{itemize}
\item She brings 3, 4, or 5 dogs.
\item She brings a positive number of songbirds, which always come in
pairs.
\item She may or may not bring her alligator, Freddy.
\end{itemize}
%
Let $T_n$ denote the number of different collections of $n$ pets that
can accompany her.  For example, $T_6 = 2$ since there are 2 possible
collections of 6 pets:
%
\begin{itemize}
\item 3 dogs, 2 songbirds, 1 alligator
\item 4 dogs, 2 songbirds, 0 alligators
\end{itemize}
%
Give a closed-form generating function for the sequence $\seq{T_0,\
T_1,\ T_2,\ T_3,\ \ldots}$.  The answer alone is sufficient, but we
can only award partial credit if you show your work.

\solution{
\begin{align*}
T(x) & = \underbrace{(x^3 + x^4 + x^5)}_{\text{collections of dogs}} \cdot
         \underbrace{(x^2 + x^4 + x^6 + x^8 + \ldots)}_{\text{collections of songbirds}} \cdot
         \underbrace{(1 + x)}_{\text{collections of gators}} \\
     & = (x^3 + x^4 + x^5) \cdot \frac{x^2}{1 - x^2} \cdot (1 + x) \\
     & = \frac{x^5 + x^6 + x^7}{1 - x}
\end{align*}
%
The second equation follows from the formula for the sum of a
geometric series.  The last step is a simplification, which is not
required for full credit.}
\end{problem}




\end{document}

