\documentstyle[12pt,psfig]{cmu-art}
%\setlength{\textwidth}{6.50in}
%\addtolength{\oddsidemargin}{-0.75in}
%\addtolength{\evensidemargin}{-0.75in}
%\topmargin -1in
\begin{document}
\centerline{\psfig{figure=tpi.eps,height=1.0in,width=4.0in}}
{\large
\fbox{\parbox{6.1in}{
\hbox to \hsize{\ \ \ QUIZ 1 \hfil Bruce Maggs \hfil Feb 23, 1997\ \ \ }

\vskip 0.1in
}}}

\noindent
{\bf NAME :} \\ \\
{\bf ANDREW ID :} \\ \\
{\bf SECTION :  \ \ A \ \ B \ \ C \ \ D} \\

\noindent
{\bf INSTRUCTIONS. For the first 7 problems you do not need to give
any reason or justification for your answers. For the remaining
problems you must give complete explanations. WRITE CLEARLY.  WRITE
YOUR NAME AND ANDREW ID ABOVE AND CIRCLE YOUR SECTION.


\newcommand{\problem}[3]{\noindent {\bf #1}. [#2 points] \\ #3 \vspace{24ex}}

\newcommand{\wisdom}[2]{\begin{quotation}
 \begin{center} \bf #1 \end{center} #2 \end{quotation} }

\wisdom{Repeat After Me.}{This part is to test your ability to study 
material that has been pre-digested and labeled as useful or
likely to appear on exams. If you do not do well on this section, your
study habits could use adjustment.}

\problem{1}{5}
{What is $6 + 12 + 18 + 24 + \cdots + (6\cdot n)$ (for any integer
$n > 0$)?}

\problem{2}{5}
{
What is $1 + \frac{1}{3} + \frac{1}{3^2} + \frac{1}{3^3} +  \cdots $?
}

\newpage

\problem{3}{5}
{
How many ways are there to rearrange the letters in MISSISSIPPI?
}

\problem{4}{5}
{
How many subsets of $\{1,2,3,4,5,6,7,8,9\}$ are there?
}

\problem{5}{5}
{
How many subsets of $\{1,2,3,4,5,6,7,8,9\}$ 
have an even number of elements?
}

\problem{6}{5}
{
Write down a formula for the number of ways to choose $m$ people from
a set of $n$, when the order of selection matters.
}

% 7.  If a chicken and a half lays an egg and a half in a day and a
% half, how many eggs will three chickens lay in three days?

\newpage

\wisdom{Reading Solutions.}{This section tests your ability to read the
homework solutions that we hand out.}

\problem{7}{10}
{What is the maximum number of days that the Traditional Marriage
Algorithm will take to terminate when there are $n$ boys and $n$
girls?  Remember that it will always take at least one day.}

\problem{8}{10}
{
Prove that $f(x) = 2x - 1$ solves the following recurrence
relation: $f(x) = 2f(x/2) + 1$, $f(1) = 1$.
}

\newpage

\wisdom{Basic Techniques.}{This part will test your ability to apply techniques
for which I have given explicit recipes. If you do not do well on this section,
your study habits could use adjustment.}

\problem{9}{10}
{
Give a closed-form solution to the following recurrence.  Show your
work.

\begin{eqnarray*}
f(n) & = & 8f(n-1) - 15f(n-2) \\
f(0) & = & 0 \\
f(1) & = & 4
\end{eqnarray*}
}

\wisdom{A Moment's Thought!}
{This section tests your ability to think a little
bit more insightfully. You must give complete explanations of your answers.} 



\problem{10}{5}
{Show how to compute $11^4$ using the binomial theorem.}

\newpage

\problem{11}{10}
{
Prove that $\{2^i\}$, where $i$ is any integer, is a group with respect
to multiplication.
}

\problem{12}{10}
{6 college suitemates order three pizzas, each with 12 slices. 
If each student must eat an even number of slices, how many ways
are there to allocate the pizza slices to the students?}

\problem{13}{15}
{Suppose that in the city walk problem, you now have the option of
going diagonally through any city block, instead of going north
or east.  How many paths are there from the origin ($0$th St.\ and
$0$th Avenue) to your home at $y$'th St.\ and $x$'th Avenue?  You may
leave your answer as a summation.
}


\end{document}


