\magnification=\magstep1
\centerline{Mathematics 357 -- Combinatorics}
\centerline{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 = 12$ months in a year, so make those the pigeonholes.
``Place'' each person (the ``pigeons'') into the proper pigeonhole based on 
which month 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 12}\rfloor = 3$.  The smallest $m$ for 
which this is true is $m = 3\times 12 + 1 = 37$.
\bigskip
\noindent
II.  A)  Any of the $100$ people present can win the $\$50$ prize.
But then he/she cannot win the others.  So there are $99$
possible winners for the $\$25$ prize (once the first prize
winner is selected), and $98$ possible winners for the third
prize (after the first and second are selected).  Thus 
(Multiplication Rule), the total number of different 
assignments of prizes to guests is:
$$100\cdot 99 \cdot 98 = P(100,3).$$
\bigskip
\noindent
B)  Like A, except that after the first prize ($\$50$)
is selected, any one of the 100 people can win the 
second and third prizes too:
$$100\cdot 100\cdot 100 = 100^3$$
different 
assignments of prizes to guests.
\bigskip
\noindent
C)  Now, the prizes are {\it not distinguishable}
by the dollar amounts
because they are all $\$20$.  We are just choosing
three distinct people out of the 100 to give
the prizes to. That means 
we need to take the answer to part A and 
divide by $3!$:
$${100\cdot 99 \cdot 98\over 3!} = {100\choose 3}$$
\bigskip
\noindent
Note: In the first two cases, since the prizes are
distinguishable (by the dollar amounts), we can list 
them in a particular order and we are using the 
general formulas for {\it permutations}.  Part
A is the formula for permutations from an ordinary
set; part B is the same as the formula for 3-permutations
from a multiset $\{\infty\cdot a_1, \ldots, \infty\cdot a_{100}\}$
since when we replace the winners in the pool we are in
effect allowing infinite repetition numbers for the 
selection of the prize winners.  Likewise,
with equal prize amounts, there is now no particular
ordering of the winners, and we are dealing with
3-combinations from a set with 100 elements.

\bigskip
\noindent
III.  A)  There are ${10\choose 6}$ ways to select $6$ slips
from the first $10$.  Similarly there are ${20\choose 4}$
to select $4$ slips from the remaining 20.  Since each choice
of the first 6 can be made together with every possible
choice of the other 4, we use the Multiplication Rule:
$${10\choose 6}\cdot {20\choose 4}$$
\bigskip
\noindent
B) We need a different approach for this part.  After
the 7 slips are removed, $30 - 7 = 23$ remain, divided
into $8$ ``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,\ldots,x_8$.  We must have
$$x_1 + x_2 + \cdots + x_8 = 23,$$     
where $x_1, x_8 \ge 0$ (we might not have any slips in the 
first and eighth groups), and $x_2, x_3, \cdots, x_7 \ge 2$
(this is where we incorporate the requirement that there 
must be at least two slips between each pair that we choose).  
Letting $y_1 = x_1$, $y_j = x_j - 2$ for each $2\le j\le 7$,
and $y_8 = x_8$, this means we need to count the number
of solutions of 
$$y_1 + y_2 +\cdots + y_8 = 11$$
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
$${ 11 + (8 - 1)\choose (8 - 1)} = { 18\choose 7}.$$
\bigskip
\noindent
IV.  If we select the $k$ houses to be painted first,
then choose one of the two possible colors 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$ houses,
we can select any number $0\le j\le k$ to be painted
green (say), then from the remaining $n - j$ select
$k - j$ to be painted blue.  This gives a partition
of the set we want to count by the number of houses
that are painted green.   By the Addition Rule,
the total number of different ways the selection 
and painting 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 
