\documentclass[12pt]{article}
\usepackage{amsmath}

\input{macros-course}

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

\newcommand{\solution}[1]{}
%\newcommand{\solution}[1]{\smallskip \textbf{Solution:} #1}

\newcommand{\pts}[1]{\relax[#1 pts]\enskip\ignorespaces}

\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

\newcommand{\bij}{\mathop{\mbox{\rm bij}}}

\begin{document}

\handout{q2}{Quiz 2}{April 14, 1999}

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

\textbf{Circle the name of your TA}:\\
\begin{center}
\begin{tabular}{lll}
Matt Blum & Stas Jarecki\&Eric Lehman & Amit Khetan\\
Mike Leonida & Zulfi Ramzan & Jared Smith-Mickelson
\end{tabular}
\end{center}

\medskip

\begin{closeitemize}
\item This quiz is \textbf{closed} book, except for a one-page sheet of
notes you have prepared.  No calculators either.

\item There are six (6) problems totaling 100 points.  Problem parts are
labelled with their point values.

\item Put your name on the top of {\bf every} page --- \emph{these pages
will 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.

\iffalse
\item Show your work, as partial credit will be given.  You will be
graded not only on the correctness of your answer, but also on the
clarity with which you express it.  {\bf Be neat}.
\fi

\item GOOD LUCK!
\end{closeitemize}

\bigskip

\iffalse
\noindent Write the hour at when your Friday recitation begins \brule{3em}

\medskip
\fi

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

\medskip

\begin{center}
\renewcommand{\arraystretch}{.3}
\begin{tabular}{|c|c|c|c|}
\hline
& &\hspace*{1in}&\\
Problem & Points & Grade & Grader\\
& & & \\ \hline \hline
& & & \\
1 &  12 & & \\ & & & \\\hline & & &\\
2 &  20 & & \\ & & & \\\hline & & &\\
3 &  20 & & \\ & & & \\\hline & & &\\
4 &  15 & & \\ & & & \\\hline & & &\\
5 &  13 & & \\ & & & \\\hline & & &\\
6 &  20 & & \\ & & &\\
\hline
\hline
& & &\\
Total & 100 & & \\
& & &\\
\hline
\end{tabular}
\end{center}

\newpage

\begin{problems}

\problem\pts{12} \emph{Divide and Conquer.}

The easily-applied version of the Master Theorem for Divide and Conquer
recurrences given in tutorial is stated below.  In the indicated space
next to each of the following recurrences, write an ``X'' if this Master
Theorem does not directly apply to it.  If it does directly apply, then
write the $\Theta()$ bound given by the Theorem for this recurrence.

\[\begin{array}{rclrclr}
T(n) & = & 3T(\ceil{n/2}) + n^{\log_2 3} & \brule{2.0in}\\
& \\
& \\
T(n) & = & T(n) - n^2 & \brule{2.0in}\\
&\\
& \\
T(n) & = & 3T(\ceil{n/2}) + n\log_2 n & \brule{2.0in}\\
& \\
& \\
T(n) & = & 3T(n-1) + 2T(n-2) & \brule{2.0in}\\
& \\
& \\
T(n) & = & 3T(\ceil{n/2}) + n^{\log_2 3}\log_2 n & \brule{2.0in}\\
& \\
& \\
T(n) & = & \frac{1}{2}T(\ceil{n/2}) + 1/\sqrt{n} & \brule{2.0in}\\
& \\
& \\
T(n) & = & 2T(\ceil{n/2}) + n^{\log_2 3} & \brule{2.0in}\\
& \\
& \\
T(n) & = & T(\ceil{n/5}) + T(\ceil{3n/4}) + 11 & \brule{2.0in}
\end{array}\]

\begin{theorem*}[Divide-And-Conquer Master Theorem]
\label{master}
Suppose
\[
T(n) = aT(\ceil{n/b}) + f(n)
\]
where $T,f:\naturals\to \reals, a > 0,$ and $b >1$.
Let $\beta ::= \log_b a$.  Then
\[
T(n) = \left\{ \begin{array}{ll}
\Theta(n^\beta) & \mbox{ if } f(n) = O(n^\alpha)\mbox{ for some } \alpha < \beta,\\
\Theta(n^\beta \log n) & \mbox{ if } f(n) = \Theta(n^\beta),\\
\Theta(n^\alpha) & \mbox{ if } f(n) = \Theta(n^\alpha) \mbox{ for some } \alpha > \beta.\\
\end{array} \right.
\]
\end{theorem*}


\newpage
\problem\pts{20}\emph{Linear Recurrences.}
\bparts
\ppart\pts{6} What is the general form of solution for the linear homogenous equation
\[
T(n) = T(n-1) + 14T(n-2) - 24T(n-3)
\]

\solution{$x^3 - x^2 - 14x + 24 = (x-2)(x-3)(x+4)$ so general solution is
$a2^n + b3^n +c(-4)^n$.}

\vspace{1.5in}


\ppart\pts{6} Find a solution for the equation
\[
T(n) = T(n-1) + 14T(n-2) -24T(n-3) + 30
\]

\solution{T(n)=3.}
\vspace{1in}

\ppart\pts{8} Now find a solution for the previous equation subject to the
boundary conditions $T(0)=6, T(1)=4,T(2)=32$.

\solution{$a=b=c=1$.}

\vfill

\eparts

\newpage

\problem\pts{10} \emph{Bijections.}
\bparts

\ppart\pts{8} Give an example of three infinite sets, none of which has a
bijection to either of the others.

\solution{$A, P(A), P(P(A))$ for any infinite set $A$.}

\vspace{2in}

\ppart\pts{10} Define explicitly, or prove there exists, a bijection
between the open unit interval $(0,1)::= \set{x \in \reals \mid 0 < x <1}$
and the closed unit interval $[0,1]::= \set{x \in \reals \mid 0 \leq x
\leq 1}$.

\solution{Define a bijection $f : [0,1] \to (0,1)$ as follows:
\[
f(x) = \left\{
         \begin{array}{ll}
          1/2 & \mbox{if } x = 0, \\
          1/4 & \mbox{if } x = 1, \\
          2^{-(n+2)} & \mbox{if } x = 2^{-n} \mbox{ for some }n>0, \\
          x & \mbox{otherwise}.
         \end{array}
       \right.
\]

Alternatively, we know from Pset 8 that $\reals \bij [0,1]$.  But $g(x) ::
= \tan \pi (x - 1/2)$ is a bijection between $\reals$ and $(0,1)$.

Alternatively, the identity function is an injection from $(0,1)$ to
$[0,1]$ and $g(x) ::= x/2 + 1/4$ is an injection from $[0,1]$ to
$(0,1)$, so by the Schr\"oder-Bernstein Theorem, there is a bijection
between them.
}

\eparts

\vfill

\newpage
\problem\pts{15} \emph{Inclusion-exclusion.}

There are 130 students in 6.042.  Some students are blessed with one or
more of the qualities of being healthy, wealthy, and/or lucky.  A few
students are cursed by the lack of all these qualities.  Moreover,
\begin{enumerate}

\item every student that is both healthy and wealthy is also lucky,

\item half of the lucky students are healthy,

\item half of the lucky students are wealthy,

\item seventy (70) students are healthy, and

\item thirty (30) students are wealthy.

\end{enumerate}
Exactly how many cursed students are there in 6.042?

\solution{
By inclusion-exclusion, we have:
\[
\card{\mbox{blessed students}} = H + W + L - HW - HL - WL + HWL
\]
where the letter strings on the right side represent cardinalities of
intersections, e.g., $HW = \card{\mbox{students who are healthy and
wealthy}}$.

Fact 1 implies that $HW = HWL$, and thus these two
terms cancel, leaving:

\[
\card{\mbox{blessed students}} = H + W + L - HL - WL
\]

Facts 2 and 3 imply that $HL = L / 2$ and $WL = L / 2$.  Substitution
gives:

\[
\card{\mbox{blessed students}} = H + W + L - (L / 2) - (L / 2)
      = H + W = 70 + 30 = 100.
\]
Fact 4 now gives the final answer:

\[
\card{\mbox{cursed students}}= 130 - \card{\mbox{blessed
      students}} = 30.
\]}

\newpage
\problem\pts{13} \emph{Multinomial coefficients.}  Remember that the
number of ways of choosing $r = r_1 + r_2 + \dots + r_n$ items \emph{with
repetition} from a set of $n$ items, with $r_i$ repetitions of the $i$th
item, is
\[
\binom{r}{r_1, \ r_2, \ \dots, \ r_n} ::=
 \frac{r!}{r_1!  r_2!  \dots  r_n!}
\]

\bparts

\ppart\pts{4} Give a simple algebraic proof that
\[
\binom{a+b+c+d}{a} \binom{b+c+d}{b,c,d} 
 = \binom{a+b+c+d}{d} \binom{a+b+c}{c} \binom{a+b}{b}.
\]



\vfill

\newpage

\ppart\pts{9} Now give a combinatorial argument proving this equation.
That is, describe two different procedures for counting the same things,
where the lefthand side of the equation clearly describes the number of
outcomes of the first procedure and the righthand side the number of
outcomes of the second procedure.

\solution{Both expressions equal $\binom{a+b+c+d}{a,b,c,d}$ and correspond
to choosing a set of four kinds of items in quantities $a,b,c$ and $d$,
respectively.  Now the LHS corresponds to first choosing $a$ of the first
kind, then $b,c$, and $d$ of the remaining three kinds.  The RHS
corresponds to first choosing $d$ of the fourth kind, then $c$ of the
third kind, and then $b$ of the second kind.}

\vfill

\eparts

\newpage
\problem\pts{20} \emph{Stars and Bars.}  The \emph{king positioning} in an
arrangement of a deck of 52 playing cards is the sequence of numerical
positions in the deck, from one to 52, of the four successive kings.  For
example, the king positioning $(1,2,3,4)$ means all the kings come at the
beginning of the deck.  The king positioning $(1,18,35,52)$ describes the
situation in which the kings are spaced uniformly---with exactly 16 cards
between successive kings.

Your answer to each of the following questions may be an arithmetic
expression involving factorials and/or multinomial coefficients.

\bparts
\ppart\pts{5} How many king positionings are there?

\solution{$\binom{52}{4}$.}

\vspace{1.5in}

\ppart\pts{7} How many king positionings are there in which \emph{no two
kings are adjacent}?

\solution{Think of kings as bars and the remaining 48 cards as stars.
Place one star between each two adjacent kings (bars).  This requires
three stars and leaves 45 stars that can be placed anywhere; there are
$\binom{45+4}{4}$ ways to do this.}

\vspace{1.5in}

\ppart\pts{8} Of the $52!$ possible arrangements of the deck, how many
have no two kings adjacent?

\solution{Now in each of the previous patterns of stars and bars, the
kings can be permuted in $4!$ ways and the remaining cards can be permuted
in $48!$ ways, so the total number of desired arrangements is
\[\binom{45+4}{4} 48!\, 4! = 49!\, 48!/45! = 48!\, P(49,4).\]

\iffalse
The form of the RHS suggests that there is another way to do this count,
but I haven't had time to figure what it is.
\fi
}

\eparts

\vfill
\end{problems}

\end{document}
