% summations
%   x geometric
%   - harmonic
%   - arithmetic
% generating functions
%   - counting
%   x formulation
%   x recurrences
% recurrences
%   x setting up
%   x solving
% counting
%   x typical sequence problems
%   x inclusion-exclusion
%   x pigeonhole principle
%   - combinatorial proof
% asymptotic notation
% approximations
%   x integration bounds
%   - Taylor's theorem

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

%\hidesolutions
\showsolutions

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

\begin{document}

\generic{Quiz 2}{April 13, 2005}

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

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

\begin{center}
\begin{tabular}{c@{\hspace{0.5in}}c@{\hspace{0.5in}}c}
Ishan & Christos & Grant
\end{tabular}
\end{center}

\begin{itemize}

\item \textbf{Calculators are not allowed on this exam.}

\item You may use one $8.5 \times 11$'' sheet with notes in your own
handwriting on both sides, but no other sources of information.

\item You may assume all results from lecture, the notes, problem
sets, and recitation.

\item Write your solutions in the space provided.  If you
need more space, write on the back of the sheet containing the
problem.

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

\item GOOD LUCK!

\end{itemize}

\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 & 15 & & \\ \hline
4 & 15 & & \\ \hline
5 & 20 & & \\ \hline
6 & 15 & & \\ \hline
7 & 15 & & \\ \hline
Total & 100 & & \\ \hline 
\end{tabular}
}
\end{center}

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

\newpage

\mbox{}

\vspace{1in}

\noindent {\Large \textbf{NOTE:} For this exam, a ``closed form'' is a
mathematical expression \textit{without} summation notation, product
notation, or the $\ldots$ symbol.  Factorials and binomial
coefficients \textit{may} appear in a closed form.  Some examples are
shown below.}

{\Large
\[
\begin{array}{c@{\hspace{1in}}c}
\underline{\text{Closed Forms}} & \underline{\text{NOT Closed Forms}} \\[1ex]
{\displaystyle 42} &
    {\displaystyle \sum_{k=0}^n k^2} \\[5ex]
{\displaystyle (\sqrt{x} + 1)^n} &
    {\displaystyle \prod_{i=1}^n \paren{1 + \frac{1}{i}}} \\[5ex]
{\displaystyle n! + \binom{n}{3}} &
    {\displaystyle \frac{1}{1} + \frac{1}{2} + \ldots +\frac{1}{n}}
\end{array}
\]
}

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

\newpage

\begin{problem}[10 points]
Let $S$ consist of all positive integers with no prime factor larger
than 3, and define:
%
\[
X = \sum_{k \in S} \frac{1}{k}
\]
%
Thus, the first few terms of the sum are:
%
\begin{align*}
X & = \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{6} + \frac{1}{8} + \frac{1}{9} + \frac{1}{12} + \ldots
\end{align*}

\iffalse
& = \frac{1}{2^0 3^0} + \frac{1}{2^1 3^0} + \frac{1}{2^0 3^1} + \frac{1}{2^2 3^0} + \frac{1}{2^1 3^1} + \frac{1}{2^3 3^0} + \frac{1}{2^0 3^2} + \frac{1}{2^2 3^1} + \ldots
\fi

\bparts

\ppart Write a closed-form expression in the box that makes the
equation below true.
%
\[
X = \sum_{j=0}^{\infty} \sum_{k=0}^{\infty} \quad
    \fbox{\rule[-0.35in]{0in}{0.8in}\rule{1in}{0in}}
\]

\solution[\vspace{2in}]{Every positive integer with no prime factor
larger than 3 has the form $2^j 3^k$ for some nonnegative integers $j$
and $k$.  Thus, the expression
%
\[
\frac{1}{2^j 3^k}
\]
%
makes the equation true.
}

\ppart Write a closed-form expression in the box that makes this
equation true:
%
\[
X = \fbox{\rule[-0.35in]{0in}{0.8in}\rule{1in}{0in}}
\]

\solution{We'll apply the formula for an infinite geometric sum twice.
%
\begin{align*}
\sum_{j=0}^{\infty} \sum_{k=0}^{\infty} \frac{1}{2^j 3^k}
    & = \sum_{j=0}^{\infty} \frac{1}{2^j}
        \paren{\sum_{k=0}^{\infty} \frac{1}{3^k}} \\
    & = \sum_{j=0}^{\infty} \frac{1}{2^j} \\
    & = \paren{\frac{1}{1 - 1/3}} \sum_{j=0}^{\infty} \frac{1}{2^j} \\
    & = \paren{\frac{1}{1 - 1/3}} \paren{\frac{1}{1 - 1/2}} \\
    & = 3
\end{align*}
}

\eparts

\end{problem}

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

\newpage

\begin{problem}[10 points]
Derive integrals that are closely-matching lower and upper bounds on
the sum
%
\[
\sum_{k=n}^{2n} \frac{1}{\ln k}
\]
%
where $n \geq 3$.  Justify your answers with a diagram.  \textbf{Do
not integrate.}  Your answers should be unevaluated integrals.

\bparts

\ppart Draw your diagram in the space below.  (To receive full credit,
the diagram must clearly communicate why your integral bounds are
correct.)

\solution[\vspace{4in}]{
\begin{center}
\begin{picture}(350,150)
\put(0,0){\vector(1,0){350}}
\put(0,0){\vector(0,1){150}}
\put(120.000000,0){\framebox(40.000000,72.134752){}}
\put(160.000000,0){\framebox(40.000000,62.133493){}}
%\put(200.000000,0){\framebox(40.000000,55.811063){}}
%\put(240.000000,0){\framebox(40.000000,51.389834){}}
\put(280.000000,0){\framebox(40.000000,48.089835){}}
\put(75,109.135667){\makebox(0,0){$y = \frac{1}{\ln x}$}}
%\qbezier(80.000000,144.269504)(88.019448,123.405215)(100.000000,109.135667)
\qbezier(100.000000,109.135667)(108.595099,98.898393)(120.000000,91.023923)
\qbezier(120.000000,91.023923)(128.914719,84.868789)(140.000000,79.823560)
\qbezier(140.000000,79.823560)(149.117750,75.673811)(160.000000,72.134752)
\qbezier(160.000000,72.134752)(169.257959,69.123935)(180.000000,66.485940)
\qbezier(180.000000,66.485940)(189.360482,64.187224)(200.000000,62.133493)
\qbezier(200.000000,62.133493)(209.438639,60.311567)(220.000000,58.659693)
\qbezier(220.000000,58.659693)(229.500146,57.173801)(240.000000,55.811063)
\qbezier(240.000000,55.811063)(249.549778,54.571631)(260.000000,53.424449)
\qbezier(260.000000,53.424449)(269.590649,52.371628)(280.000000,51.389834)
\qbezier(280.000000,51.389834)(289.624873,50.482032)(300.000000,49.630180)
\qbezier(300.000000,49.630180)(309.653939,48.837542)(320.000000,48.089835)
\qbezier(320.000000,48.089835)(329.678921,47.390341)(340.000000,46.727527)
\put(65,79.823560){\makebox(0,0){$y = \frac{1}{\ln(x+1)}$}}
%\qbezier(80.000000,91.023923)(88.914719,84.868789)(100.000000,79.823560)
\qbezier(100.000000,79.823560)(109.117750,75.673811)(120.000000,72.134752)
\qbezier(120.000000,72.134752)(129.257959,69.123935)(140.000000,66.485940)
\qbezier(140.000000,66.485940)(149.360482,64.187224)(160.000000,62.133493)
\qbezier(160.000000,62.133493)(169.438639,60.311567)(180.000000,58.659693)
\qbezier(180.000000,58.659693)(189.500146,57.173801)(200.000000,55.811063)
\qbezier(200.000000,55.811063)(209.549778,54.571631)(220.000000,53.424449)
\qbezier(220.000000,53.424449)(229.590649,52.371628)(240.000000,51.389834)
\qbezier(240.000000,51.389834)(249.624873,50.482032)(260.000000,49.630180)
\qbezier(260.000000,49.630180)(269.653939,48.837542)(280.000000,48.089835)
\qbezier(280.000000,48.089835)(289.678921,47.390341)(300.000000,46.727527)
\qbezier(300.000000,46.727527)(309.700618,46.104559)(320.000000,45.511961)
\qbezier(320.000000,45.511961)(329.719631,44.952721)(340.000000,44.418942)
\put(140,30){\makebox(0,0){$\frac{1}{\ln n}$}}
\put(180,30){\makebox(0,0){$\frac{1}{\ln(n+1)}$}}
\put(300,30){\makebox(0,0){$\frac{1}{\ln(2n)}$}}
\put(120,-10){\makebox(0,0){$n-1$}}
\put(160,-10){\makebox(0,0){$n$}}
\put(320,-10){\makebox(0,0){$2n$}}
\end{picture}
\end{center}
}

\ppart Write your lower bound integral here {\Large $\rightarrow$}
\fbox{\instatements{\rule[-0.4in]{0in}{1in}\rule{2in}{0in}}\insolutions{
$\int_{n-1}^{2n} \frac{1}{\ln(x + 1)}\ dx$}}

\ppart Write your upper-bound integral here {\Large $\rightarrow$}
\fbox{\instatements{\rule[-0.4in]{0in}{1in}\rule{2in}{0in}}\insolutions{
$\int_{n-1}^{2n} \frac{1}{\ln x}\ dx$}}

\eparts

\end{problem}

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

\newpage

\newcommand{\medbox}[1]{\fbox{\rule{0in}{0.2in}\rule{0.2in}{0in}}
\ {\displaystyle \paren{#1}}
& \Theta & O & \Omega & o}
\newcommand{\symbols}{}

\begin{problem}[15 points]
Solve the following problems involving asymptotic notation.  Here
$H_n$ is the $n$-th harmonic number; thus, $H_n = 1/1 + 1/2 + \ldots +
1/n$.

\bparts

\ppart Circle \textbf{all symbols} on the right that could properly
appear in the box on the same line.  (There may be more than one!)

{\Large
\[
\begin{array}{rl@{\hspace{0.5in}}c@{\hspace{0.3in}}c@{\hspace{0.3in}}c@{\hspace{0.3in}}c}
n^2 & = \medbox{\frac{n^2 \log n}{\sqrt{n + 1}}} \\[3ex]
2^n & = \medbox{3^n - n^3} \\[3ex]
2 H_n & = \medbox{\ln n} \\[3ex]
n^{0.01} & = \medbox{(\ln n)^{100}} \\[3ex]
%\ln(n!) & = \medbox{n \ln n}
\end{array}
\]
}

\solution{(1) $\Omega$ (2) $O$, $o$ (3) $\Theta$, $O$, $\Omega$ (4) $\Omega$ (5) $O$, $o$.}

\ppart Suppose that $f(n) \sim g(n)$.  Beside each statement below
that \textit{must} be true, circle \textbf{true}.  Beside the
remaining statements, circle \textbf{false}.
%
\bigskip
\begin{center}
\begin{tabular}{l@{\hspace{0.75in}}c@{\hspace{0.75in}}c}
%{\Large $2^{f(n)} \sim 2^{g(n)}$} & \textbf{true} & \textbf{false} \\[3ex]
{\Large $f(n)^2 \sim g(n)^2$} & \textbf{true} & \textbf{false} \\[3ex]
{\Large $f(n) = O(g(n))$} & \textbf{true} & \textbf{false} \\[3ex]
{\Large $f(n) = o(g(n))$} & \textbf{true} & \textbf{false} \\[3ex]
{\Large $2^{f(n)} = \Theta(2^{g(n)})$} & \textbf{true} & \textbf{false} \\
\end{tabular}
\end{center}

\solution{(a) False.  Let $f(n) = n$, $g(n) = n + 1$.  (b) True.  (c)
True.  (d) False for all $f, g$.  (e) False.  Let $f(n) = n$, $g(n) =
n + \log n$.}

\eparts

\end{problem}

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

\newpage

\begin{problem}[15 points]
A misguided MIT student designs a self-replicating 6.270 robot.  The
student builds one such robot every day, starting on day 0.  The day
after a robot is built, it constructs two copies of itself.  (On all
subsequent days, the robot busily searches for ping-pong balls---
these are 6.270 robots, after all.)  Here is what happens over the
first few days:
%
\begin{description}

\item[Day 0.] The student builds robot $R_1$.

\item[Day 1.] The student builds robot $R_2$.  Robot $R_1$ builds
robots $R_3$ and $R_4$.

\item[Day 2.] The student builds $R_5$.  Robot $R_2$ builds $R_6$ and
$R_7$, robot $R_3$ builds $R_8$ and $R_9$, and robot $R_4$ builds
$R_{10}$ and $R_{11}$.  Robot $R_1$ searches for ping-pong balls.

\item[Day 3.]  The student builds $R_{12}$.  Robots $R_5, \ldots,
R_{11}$ build robots $R_{13}, \ldots, R_{26}$.  Robots $R_1$, $R_2$,
$R_3$, and $R_4$ search for ping-pong balls.

\end{description}
%
Let $T_n$ be the number of robots in existence at the end of day $n$.
Thus, $T_0 = 1$, $T_1 = 4$, $T_2 = 11$, and $T_3 = 26$.

\bparts

\ppart How many new robots are built on day $n-1$?  Express your
answer in terms of the variables $T_{n-1}, T_{n-2}, \ldots$ and assume
$n \geq 2$.

\solution[\vspace{1.75in}]{This is the difference between the number
that existed on day $n-1$ and the number that existed on day $n-2$,
which is $T_{n-1} - T_{n-2}$.}

\ppart Express $T_n$ with a recurrence equation and sufficient base
cases.  \textbf{Do not solve the recurrence.}

\solution{The number of robots on day $n$ is equal to the number of
robots on day $n-1$, plus twice the number of robots built yesterday
($T_{n-1} - T_{n-2}$), plus the 1 robot built by the student.
Therefore, we have:
%
\begin{align*}
T_0 & = 1 \\
T_1 & = 3 \\
T_n & = 3 T_{n-1} - 2 T_{n-2} + 1 \quad (\text{for } n \geq 2)
\end{align*}
}

\newpage

\ppart An even more misguided 6.270 student designs another
self-replicating robot to hunt down and destroy robots of the first
kind.  The number of these robots at the end of day $n$ is $P_n$,
where:
%
\begin{align*}
P_0 & = 0 \\
P_1 & = 1 \\
P_n & = 5 P_{n-1} - 6 P_{n-2} + 1 \quad (\text{for } n \geq 2)
\end{align*}
%
Find a closed-form expression for $P_n$.  Show your work clearly to be
eligible for partial credit.

\eparts

\solution{The characteristic equation is $x^2 - 5 x + 6 = 0$.  The
right side factors into $(x - 2)(x - 3)$, so the roots are $2$ and
$3$.  For a particular solution, let's first guess $P_n = c$.
Substituting this into the recurrence equation gives $c = 5 c - 6 c +
1$, which implies that $c = 1/2$.  Therefore, the general form of the
solution is:
%
\[
P_n = A \cdot 2^n + B \cdot 3^n + 1/2
\]
%
Substituting $P_0 = 0$ and $P_1 = 1$ gives the equations:
%
\begin{align*}
0 & = A + B + 1/2 \\
1 & = 2 A + 3 B + 1/2
\end{align*}
%
Solving this system gives $A = -2$ and $B = 3/2$.  Therefore, the
solution is:
%
\[
P_n = -2 \cdot 2^n + \frac{3}{2} \cdot 3^n + 1/2
\]
}


\end{problem}

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

\newpage

\begin{problem}[20 points] Solve the following counting problems.  Your
answers must be closed forms, but need not be simplified.  In
particular, you may leave factorials and binomial coefficients in your
answers.  To be eligible for partial credit, you must explain how you
arrived at your answer.

\bparts

\ppart Four card players (Alice, Bob, Carol, and Dave) are each dealt
a 7-card hand from a 52-card deck.  In how many different ways can
this be done?

\solution[\vspace{3in}]{There is a bijection with 52-symbol sequences
containing 7 A's, 7 B's, 7 C's, 7 D's and 24 X's (indicating cards
that remain in the deck).  Thus, the number of ways to deal out the
cards is
%
\[
\frac{51!}{7!^4\ 24!}
\]
%
by the Bookkeeper Rule.}


\ppart Stinky Peterson has decided to start a Bug Farm under his bed.
He plans to raise 100 bugs selected from four basic varities:
\textit{creepy}, \textit{crawly}, \textit{fuzzy}, and \textit{slimey}.
Assuming he wants at least 10 speciments of each, how many different
distributions are possible?  (For example, one possible distribution
is 20 creepy, 20 crawly, 10 fuzzy, and 50 slimey.)

\solution[\newpage]{First, he places 10 specimens of each under his
bed.  Then he must select the remaining 60 additional speciments from
the four kinds of bug.  There is a bijection between such selections
and 63-bit sequences with exactly 3 ones, so the number of
distributions is
%
\[
\frac{63!}{60!\ 3!} = \binom{63}{60}
\]
%
by the Bookkeeper Rule.}

\ppart There are $n$ runners in a race.  Before the race, each runner
is assigned a number between 1 and $n$.  The runners can finish the
race in any one of $n!$ different orders.  In how many of these orders
is the first finisher not $\#1$, the second finisher not $\#2$, and
the third finisher not $\#3$?

\solution[\vspace{3in}]{Let $P_k$ be the set of finishing orders in
which runner $\#k$ \textit{is} is the $k$-th finisher.  In these
terms, the solution is:
%
\begin{align*}
n! - \size{P_1 \cup P_2 \cup P_3}
    & = n!  - (\size{P_1} + \size{P_2} + \size{P_3} \\
    & \qquad - \size{P_1 \cap P_2}
            - \size{P_1 \cap P_3}
            - \size{P_2 \cap P_3} \\
    & \qquad + \size{P_1 \cap P_2 \cap P_3}) \\
    & = n! - 3 (n-1)! + 3 (n-2)! - (n-3)!
\end{align*}
}

\ppart How many ways are there to park 4 identical SUVs and 10
identical cars in a row of 20 parking spaces if SUVs are too wide to
park next to each other?  For example, here is one parking
possibility:
%
\begin{center}
\begin{picture}(400,40)
\put(10,20){\makebox(0,0){\shortstack{S\\U\\V}}}
\put(50,20){\makebox(0,0){\shortstack{c\\a\\r}}}
\put(70,20){\makebox(0,0){\shortstack{c\\a\\r}}}
\put(130,20){\makebox(0,0){\shortstack{c\\a\\r}}}
\put(150,20){\makebox(0,0){\shortstack{S\\U\\V}}}
\put(170,20){\makebox(0,0){\shortstack{c\\a\\r}}}
\put(190,20){\makebox(0,0){\shortstack{S\\U\\V}}}
\put(230,20){\makebox(0,0){\shortstack{c\\a\\r}}}
\put(250,20){\makebox(0,0){\shortstack{c\\a\\r}}}
\put(290,20){\makebox(0,0){\shortstack{c\\a\\r}}}
\put(330,20){\makebox(0,0){\shortstack{c\\a\\r}}}
\put(350,20){\makebox(0,0){\shortstack{S\\U\\V}}}
\put(370,20){\makebox(0,0){\shortstack{c\\a\\r}}}
\put(390,20){\makebox(0,0){\shortstack{c\\a\\r}}}
\multiput(0,0)(20,0){21}{\line(0,1){40}}
\line(1,0){400}
\end{picture}
\end{center}

\solution[\newpage]{First, let's park the SUVs.  The number of ways to
do this is equal to the number of ways to select 20 books off of a
shelf such that adjacent books are not selected--- a problem of a type
you've seen before.  The answer is $\binom{17}{4}$.  Now the 10 cars
can be parked in the 16 remaining spaces in $\binom{16}{10}$ ways.  So
the total number of parking possibilities is:
%
\[
\binom{17}{4} \cdot \binom{16}{10}
\]
}

\ppart A \textit{mobile} is a hanging structure built from seven
horizontal rods (indicated with solid lines), seven vertical strings
(indicated with dotted lines), and eight toys (indicated with the
letters A-H).
%
\begin{center}
\begin{picture}(220,110)(0,40)
% \put(0,40){\dashbox(220,110){}} % bounding box
\put(110,140){\oval(10,10)[b]}
\put(110,140){\oval(10,10)[tr]}
\put(110,145){\line(0,1){5}}
\qbezier[6](110,135)(110,127.5)(110,120)
\put(50,120){\line(1,0){120}}
\qbezier[10](50,120)(50,105)(50,90)
\qbezier[10](170,120)(170,105)(170,90)
\put(20,90){\line(1,0){60}}
\put(140,90){\line(1,0){60}}
\qbezier[10](20,90)(20,75)(20,60)
\qbezier[10](80,90)(80,75)(80,60)
\qbezier[10](140,90)(140,75)(140,60)
\qbezier[10](200,90)(200,75)(200,60)
\put(0,60){\line(1,0){40}}
\put(60,60){\line(1,0){40}}
\put(120,60){\line(1,0){40}}
\put(180,60){\line(1,0){40}}
%\qbezier[10](0,60)(0,45)(0,30)
%\qbezier[10](40,60)(40,45)(40,30)
%\qbezier[10](60,60)(60,45)(60,30)
%\qbezier[10](100,60)(100,45)(100,30)
%\qbezier[10](120,60)(120,45)(120,30)
%\qbezier[10](160,60)(160,45)(160,30)
%\qbezier[10](180,60)(180,45)(180,30)
%\qbezier[10](220,60)(220,45)(220,30)
\put(0,60){\line(0,-1){5}}
\put(40,60){\line(0,-1){5}}
\put(60,60){\line(0,-1){5}}
\put(100,60){\line(0,-1){5}}
\put(120,60){\line(0,-1){5}}
\put(160,60){\line(0,-1){5}}
\put(180,60){\line(0,-1){5}}
\put(220,60){\line(0,-1){5}}
\put(0,45){\makebox(0,0){\textbf{A}}}
\put(40,45){\makebox(0,0){\textbf{B}}}
\put(60,45){\makebox(0,0){\textbf{C}}}
\put(100,45){\makebox(0,0){\textbf{D}}}
\put(120,45){\makebox(0,0){\textbf{E}}}
\put(160,45){\makebox(0,0){\textbf{F}}}
\put(180,45){\makebox(0,0){\textbf{G}}}
\put(220,45){\makebox(0,0){\textbf{H}}}
\put(0,75){\vector(1,0){15}}
\put(190,105){\vector(-1,0){15}}
\end{picture}
\end{center}
%
Many different toy arrangements can be obtained by twisting the
strings.  For example, twisting the string marked with the
$\rightarrow$ arrow would swap toys \textbf{A} and \textbf{B}.
Twisting the string marked with the $\leftarrow$ arrow would
\textit{reverse} the order of toys \textbf{E}, \textbf{F}, \textbf{G},
and \textbf{H}.  On the other hand, no combination of twists swaps
only toys \textbf{B} and \textbf{C}.  Two mobiles are different if one
can not be obtained from the other by twisting strings.  How many
different mobiles are possible?

\solution{There are $8!$ different sequences of toys.  Each mobile can
be configured in $2^7$ different ways, by twisting or not twisting the
7 upper strings.  Thus, there is a $2^7$-to-1 mapping from sequences
to mobiles.  By the Division Rule, the number of different mobiles is
$8!/2^7 = 315$.}

\eparts

\end{problem}

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

\iffalse

\newpage

\begin{problem}
The sum of two sequences is obtained by adding corresponding terms:
%
\[
(a_1, a_2, \ldots, a_k) + (b_1, b_2, \ldots, b_k) =
    (a_1 + b_1, a_2 + b_2, \ldots, a_k + b_k)
\]
%
Let $S$ be a set of 4-bit sequences.  Prove that if $\size{S} \geq
20$, then there must exist two different subsets of $S$ with the same
sum.  Fact: $2^{10} > 1000$.

\solution{Suppose that $\size{S} = n$.  The number of different
subsets is $2^n$.  The number of different subset sums is $(n+1)^4$.
For $n = 20$, $2^n > 1000^2 > \paren{21^2}^2 = (n+1)^4$.  So, by the
Pigeonhole Principle, there must exist two different subsets with the
same sum.}

\end{problem}

\fi

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

\newpage

\newcommand{\smallbox}{\fbox{\rule{0in}{0.2in}\rule{0.15in}{0in}}}

\begin{problem}[15 points]
A \textit{subsequence} is obtained from a sequence by deleting one or
more terms.  For example, the sequence $(1, 2, 3, 4, 5)$ contains $(2,
4, 5)$ as a subsequence.

\begin{theorem*}
Every sequence of $n^2+1$ distinct integers contains an increasing or
decreasing subsequence of length $n + 1$.
\end{theorem*}

\noindent For example, in the $3^2 + 1 = 10$ term sequence
$(5, 6, \underline{1}, \underline{4}, 9, 0, 2,
    \underline{7}, \underline{8}, 3)$,
the underlined terms form an increasing sequence of length $3 + 1 =
4$.  Fill in the outline of a proof provided below.

\noindent \textit{Proof.}

\bparts

\ppart Label each term in the sequence with the length of the longest
increasing subsequence that ends with that term.  For example, here is
a sequence with the correponding labels listed below.
%
\[
\begin{array}{r@{\hspace{0.25ex}}cccccccccc@{\hspace{0.25ex}}l}
( & 2, & 6, & 1, & 5, & 4, & 9, & 0, & 8, & 3, & 7 & ) \\[0.5ex]
  & \fbox{{\text {\LARGE 1}}} & \fbox{{\text {\LARGE 2}}} & \fbox{{\text {\LARGE1}}} & \smallbox & \smallbox 
  & \smallbox & \smallbox & \smallbox & \smallbox & \smallbox
\end{array}
\]

\solution{
\[
1, 2, 1, 2, 2, 3, 1, 3, 2, 3
\]
}

\ppart Now there are two cases.  If some term is labeled $n+1$ or
higher, then the theorem is true because

\instatements{\noindent \fbox{{\rule{0in}{2in}\rule{5.75in}{0in}}}}

\solution{this means there is an increasing sequence of length at
least $n+1$ that ends with that term.}

\ppart Otherwise, at least $n+1$ terms must have the same label $b \in
\set{1, 2, \ldots, n}$ because

\instatements{\noindent
\fbox{\rule{0in}{2in}\rule{5.75in}{0in}}}

\solution[\newpage]{of the Pigeonhole Principle.  Regard the labels a pigeons
and the numbers $1, 2, \ldots, n$ as pigeonholes.  Assign each label
to its value.  Since there are $n^2+1$ pigeons and only $n$
pigeonholes, some $n+1$ pigeons must be assigned to some hole $b$.}

\ppart The theorem is also true in this case because

\instatements{\noindent
\fbox{\instatements{\rule{0in}{3in}\rule{5.75in}{0in}}}}

\solution{Each of the $n+1$ terms labeled $b$ must be smaller than the
one before.  (Otherwise, a term labeled $b$ could be appended to the
length-$b$ increasing sequence that ends at its predecessor to obtain
a length-$(b+1)$ increasing sequence.  But then the term should
actually be labeled $b+1$.)  Therefore, the $n+1$ terms labeled $b$
form a decreasing subsequence.}

\eparts

\hfill $\Box$

\end{problem}

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

\newpage

\begin{problem}[15 points]
Every day in the life of Dangerous Dan is a potential disaster:
%
\begin{itemize}

\item Dan may or may not spill his breakfast cereal on his computer
keyboard.

\item Dan may or may not fall down the front steps on his way out the
door.

\item Dan stubs his toe zero or more times.

\item Dan blurts something foolish an even number of times.

\end{itemize}
%
Let $T_n$ be the number of different combinations of $n$ mishaps Dan
can suffer in one day.  For example, $T_3 = 7$, because there are
seven possible combinations of three mishaps:
%
\[
\begin{array}{rccccccc}
\text{spills} & 0 & 1 & 0 & 1 & 1 & 0 & 0 \\
\text{falls}  & 0 & 0 & 1 & 1 & 0 & 1 & 0 \\
\text{stubs}  & 3 & 2 & 2 & 1 & 0 & 0 & 1 \\
\text{blurts} & 0 & 0 & 0 & 0 & 2 & 2 & 2
\end{array}
\]

\bparts

\iffalse
\ppart Fill in the boxes below with the correct quantities.
%
\[
T_0 = \fbox{\rule{0.75in}{0in}\rule[-0.3in]{0in}{0.75in}} \qquad
T_1 = \fbox{\rule{0.75in}{0in}\rule[-0.3in]{0in}{0.75in}} \qquad
T_2 = \fbox{\rule{0.75in}{0in}\rule[-0.3in]{0in}{0.75in}}
\]

\solution[\vspace{1.5in}]{$T_0 = 1$, $T_1 = 3$, $T_2 = 4$}
\fi

\ppart Give a generating function $g(x)$ for the sequence $\set{T_0,
T_1, T_2, \ldots}$.

\solution[\vspace{2in}]{
\[
\frac{(1+x)^2}{(1-x)(1-x^2) = \frac{1+x}{(1-x)^2}}
\]
}

\ppart Put integers in the boxes that make this equation true:
%
{\Large
\[
g(x) = \frac{\frame{\rule{0.75in}{0in}\rule{0in}{0.75in}}}{1-x}
     + \frac{\frame{\rule{0.75in}{0in}\rule{0in}{0.75in}}}{(1-x)^2}
\]}

\solution[\newpage]{$-1, 2$}

\ppart Put a closed-form expression in the box that makes this
equation true:
%
{\Large
\[
T_n = \fbox{\rule[-0.4in]{0in}{1in}\rule{2in}{0in}}
\]
}
%
Remember that $1/(1-x)^2$ generates the sequence $\seq{1, 2, 3, \ldots}$.

\solution{
$2(n+1)-1 = 2n + 1$
}

\eparts

\end{problem}

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

\end{document}
