\magnification=\magstep1
\centerline{Mathematics 357 -- Combinatorics}
\centerline{Makeup Midterm 1 Solutions}
\centerline{February 28, 2005}
\bigskip
\noindent
I.  A)  This is one form of the Strong Pigeonhole
Principle (see the class notes!)  By far the most economical 
way to prove this statement is {\it by contradiction}. 
So suppose that $m$ pigeons are placed into $k$ pigeonholes, 
but no hole has more than $\lfloor {m-1\over k} \rfloor$ 
pigeons, or in other words, that the number of pigeons
in each hole is 
$$\le \lfloor {m-1\over k}\rfloor.$$  
Counting the total number of pigeons in all $k$ of the 
pigeonholes, we see that 
there can be at most:
$$k \cdot \lfloor {m-1\over k} \rfloor \le k \cdot {m-1\over k} = m-1$$
of them.  This is a contradiction because we said
$m$ pigeons were placed.

\bigskip
\noindent
Note:  There is no need for separate cases based on the size of $m$,
etc.  The formula works in all cases.  For instance, if $m < k$, 
there must be one hole with more than $0$ pigeons (so $\ge 1$).  
\bigskip
\noindent
B) There are $k = 52$ weeks in a year, so make those the pigeonholes.
``Place'' each person (the ``pigeons'') into the proper pigeonhole based on 
which week his/her birthday falls in.  By part A, some pigeonhole
will contain more than 3 pigeons (i.e. 4 or more) as soon as
$\lfloor {m-1\over 52}\rfloor = 3$.  The smallest $m$ for 
which this is true is $m = 3\times 52 + 1 = 157$.
\bigskip
\noindent
II.  A) The answer here is the same as the number of 
$3$-combinations of the multiset 
$\{\infty\cdot a_1, \ldots, \infty\cdot a_{150}\}$
(where the 150 elements represent the 150 guests.  This number is
$${3 + (150 - 1) \choose (150 - 1)} = {152\choose 149} = {152\choose 3}$$
(Note:  You can also derive this from scratch as follows.  There
are $150 = {150\choose 1}$ ways for one person to win all three
prizes; there are $2{150\choose 2}$ for one person to get one prize
and one to get two prizes.  Finally there are ${150 \choose 3}$
ways for three distinct people to get the prizes.  Adding, we get
$${150\choose 1} + 2{150\choose 2} + {150 \choose 3} = {152\choose 3}$$
(by the Pascal's Triangle identity, or Vandermonde convolution).  
\bigskip
\noindent
B)  Answer is $150^3$ (selection with replacement, but now
since the prizes are different, we are in effect talking
about a 3-permutation, not a 3-combination.)
\bigskip
\noindent
C)  Answer is $150 \cdot 149 \cdot 148 = P(150,3)$,
since there are 150 people who can win the first prize
($\$50$), then 149 people who can win the second prize
(once the first prize winner is chosen), and 148 who can win the third
(once the first and second prize winners are chosen).

\bigskip
\noindent
III.  A)  There are ${12\choose 5}$ ways to select $5$ slips
from the first $12$.  Similarly there are ${13\choose 3}$
to select $3$ slips from the remaining $13$.  Since each choice
of the first 5 can be made together with every possible
choice of the other 3, we use the Multiplication Rule:
$${12\choose 5}\cdot {13\choose 3}$$
\bigskip
\noindent
B) We need a different approach for this part.  After
the 3 slips are removed, $25 - 3 = 22$ remain, divided
into $4$ ``groups'': those before the first one removed,
those between the first and second, those between the second
and the third, and those after
the last one removed.  Call the numbers of slips in each
of these groups $x_1,x_2,x_3,x_4$.  We must have
$$x_1 + x_2 + x_3 + x_4 = 22,$$     
where $x_1, x_4 \ge 0$ (we might not have any slips in the 
first and fourth groups), and $x_2, x_3 \ge 3$
(this is where we incorporate the requirement that there 
must be at least three slips between each pair that we choose).  
Letting $y_1 = x_1$, $y_j = x_j - 3$ for each $2\le j\le 3$,
and $y_4 = x_4$, this means we need to count the number
of solutions of 
$$y_1 + y_2 + y_3 + y_4 = 16$$
where all $y_i \ge 0$ are integers.  As we know from 
examples in class the number of solutions in nonnegative
integers of an equation of this type is
$${ 16 + (4 - 1)\choose (4 - 1)} = { 19\choose 3}.$$
\bigskip
\noindent
IV.  If we select the $k$ cars to get the fliers first,
then choose one of the two possible types for each
of them, we get the right-hand side $2^k {n\choose k}$.
On the other hand, from the whole set of $n$ cars,
we can select any number $0\le j\le k$ to get the pizzeria ad
(say), then from the remaining $n - j$ select
$k - j$ to get the car wash ad.  This gives a partition
of the set we want to count by the number of cars
that get the pizzeria ad.   By the Addition Rule,
the total number of different ways the selection 
and distribution of ads can be done, thinking about it this 
way, is:
$$\sum_{j=0}^k {n\choose j}{n - j\choose k - j} 
= {n\choose 0}{n \choose k } + {n\choose 1}{n - 1\choose k - 1}
+\cdots + {n\choose k}{n - k\choose 0}$$
The equality
$$ \sum_{j=0}^k {n\choose j}{n - j\choose k - j} = 2^k {n\choose k}$$
then follows because we are just counting the same
set in two different ways.
\bigskip
\noindent
V. We want to count the number of $n$-combinations
of the multiset $\{n\cdot a, 1\cdot b_1, \ldots, 1\cdot b_{2n+1}\}$.
Partition the collection of these $n$-combinations by {\it the number
of $a$'s} that are included, and count the number of choices for the 
$b_i$'s in each case. There are
$$\cases{ {2n + 1\choose n} & with no $a$'s\cr
          {2n + 1\choose n - 1} & with exactly one $a$\cr
                &\vdots \cr
          {2n + 1\choose n - j} & with exactly $j$ $a$'s\cr
                &\vdots \cr
          {2n + 1 \choose 0} & with $n$ $a$'s\cr}$$
By the Addition Rule, the number of $n$-combinations is
$$\sum_{j=0}^n {2n + 1\choose j}.$$
Now, notice that this is the ``first half'' of the sum
of all the binomial coefficients ${2n + 1\choose j}$
(the second half are the ones with $j = n + 1, \ldots, 2n + 1$).
By the ``symmetry relation'' ${k\choose\ell} = {k\choose k - \ell}$, and
the consequence $\sum_{j = 0}^{2n+1} {2n+1 \choose j} = 2^{2n+1}$ of the 
Binomial Theorem, we have
$$\eqalign{
2^{2n+1} &= \sum_{j=0}^{2n+1} {2n+1\choose j} \cr
         &= \sum_{j=0}^n {2n + 1 \choose j} + \sum_{j=n+1}^{2n+1} {2n+1\choose j} \cr
         &= \sum_{j=0}^n {2n + 1 \choose j} + \sum_{j=n+1}^{2n+1} {2n+1\choose 2n + 1 - j} \cr
 &= \sum_{j=0}^n {2n + 1 \choose j} + \sum_{\ell = 0}^{n}{2n+1\choose \ell}\cr
 &= 2\cdot \sum_{j=0}^n {2n + 1 \choose j} \cr
\Rightarrow 2^{2n} &= \sum_{j=0}^n {2n + 1 \choose j} \cr}$$
(At the last step, we divided by $2$ on both sides.)  This is what we wanted
to show.
\bye 
