\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 Steven Rudich \hfil Feb 19, 1996\ \ \ }

\vskip 0.1in
}}}

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

\noindent
{\bf INSTRUCTIONS. For the first 10 problems you do not need to give any reason
or justifcation for your answer. For the last two 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{30ex}}

\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 likely to appear 
on exams. If you do not do well on this section, your study habits could
use adjustment.}


\problem{1}{5}
{
Give a closed form solution to $3+6+9+\ldots + 3n$.
}

\problem{2}{5}
{
Give a closed form solution to $\sum_{i=0}^{k} X^i$.
}

\newpage

\problem{3}{5}
{
Give a formula for $n$ choose $k$.
}

\problem{4}{5}
{How many subsets can be formed from the elements of an $n$ element set?}

\problem{5}{5}
{What is the formula for the power series expansion of ${(x+y)}^n$?}

\newpage

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

\problem{6}{10}
{Show a set of bisexual dating preferences where there is no possible stable
pairing among the people.}

\problem{7}{10}
{Let $(G, \heartsuit)$ be a finite group.
Let $a$ be an element of $G$. Define $a^0 = e$, where $e$ is the identity
element of the group. For natural numbers $n>0$, define $a^n = a \heartsuit
a^{n-1}$. Define $H = \{\ a^i\ | \ i \in {\bf N}\ \}$. We know that $H$
is a subgroup of $G$. TRUE or FALSE: $H$ is {\em always} a commutative
group.}

\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.  You do not need to reduce
factorials and binomial coefficients to a numeric answer.}


\problem{8}{10}
{
How many integer solutions to the following equations?
\[ X_1 + X_2 + X_3 + X_4 + X_5 = 15,\ \  0 \leq X_i  \]
}

\problem{9}{10}
{How many 5 card hands with all cards the same suit can be formed
from an ordinary 52 card deck?}


\problem{10}{5}
{How many ways to rearrange the letters in the word EFFORTLESS?}

\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{11}{15}
{A limo is two car lengths long and a car is a single car length
long. Let $T(n)$ be the number of distinct possible ways of parking
cars and limos along a curb that is $n$ car lengths long. Order
matters, but any two cars and any two limos are considered identical.
If the curb is 4 car lengths long, then the distinct possible parking
patterns are LL, LCC, CLC, CCL, and CCCC. Thus, $T(4) = 5$. Derive
a recurrence relation for $T$ that completely determines it. No need to
put it in closed form, but justify your answer.}


\newpage

\problem{12}{15}{Joe Hacker has a binary encoding scheme capable of
representing an arbitrary 5 card poker hand. It uses 30 bits. Each card
is described by a six bit code: 2 bits for the suit and 4 bits for the
rank.  The hand is a 30 bit string listing the five cards in some
order. Cindy Cerebral tells Joe that his scheme is wasteful in terms of
number of bits used to encode a hand. ``I can do it using only 22
bits'', she says.  ``Furthermore, my scheme is the {\em best
possible}''. Briefly describe a scheme that is as good as Cindy's
scheme and prove that it really is the best possible! Hint: It is a
scheme that you know quite well. This problem is much simpler than it
first appears.}







\end{document}


