\magnification=\magstep1
\nopagenumbers
\centerline{Mathematics 357 -- Combinatorics}
\centerline{Makeup Midterm Examination 1}
\centerline{February 28, 2005}
\bigskip
\noindent
{\it Directions}
\bigskip
Do any combination of parts of the following 5 problems in the 
blue exam book.  (The exam will be scored out of 100 points, but
you have the possibility of accumulating up to 125 if you do all the 
questions.)
Explain your reasoning fully and do not place any work on the exam sheet.  
{\it Relax, and read each question carefully before starting to work!}
\bigskip
\noindent
I.  
\item{A)} (15) Show that if $m$ ``pigeons'' are placed
into $k$ ``pigeonholes,'' then some hole contains
{\it more than} $\lfloor {m-1\over k}\rfloor$ pigeons.  (Here
$\lfloor x\rfloor$ is the greatest integer $\le x$.)
\item{B)} (10) What is the {\it smallest} number of people for
which it is {\it always} true that four people in the group 
have birthdays in the same week?  (You can assume there are a whole
number of weeks in the year.)
\bigskip
\noindent
II.  150 people attend a fund-raising lunch where
each is assigned a number for a drawing for three door prizes.
Find the number of different assignments of prizes to guests if:
\bigskip
\item{A)} ($8.\overline{3}$) All three prizes are \$20 and 
after each winning number is drawn, it {\it is replaced}
in the pool of potential winners.
\item{B)} ($8.\overline{3}$) The prizes are \$50, \$25, \$10, and 
after each winning number is drawn, it {\it is replaced}
in the pool of potential winners.
\item{C)} ($8.\overline{3}$) The prizes are \$50, \$25, \$10, 
the winners are drawn in that order, and
after each winning number is drawn, it {\it is not replaced}
in the pool of potential winners.
\bigskip
\noindent
III.  Slips of paper numbered 1 to 25 are arranged side by side
on a table.
\bigskip
\item{A)} (10)  In how how many different ways can a total 
of 8 slips be selected if exactly 5 come from 
the first 12 and 3 come from the other 13?  
\item{B)} (15)  In how how many different ways can 3
slips be selected if there must be at least 3 slips
between each chosen pair?
\bigskip
\noindent
IV. (25) $k$ out of $n$ cars in a lot are selected 
and each one of those gets an advertising flier for either a 
pizzeria or a car wash.  
By counting the ways the selection and distribution of the ads
can be done using two different approaches, give a combinatorial argument 
establishing:
$${n\choose 0}{n\choose k} + {n\choose 1}{n-1\choose k-1} + \cdots 
+ {n\choose k}{n-k\choose 0} = 2^k {n\choose k}$$
\bigskip
\noindent
V. (25)  Show that there are $2^{2n}$ different $n$-combinations
of the multiset 
$$\{n\cdot a, 1\cdot b_1, \ldots, 1\cdot b_{2n+1}\}.$$
\bye