Mathematics 357 – Combinatorics Makeup Midterm 1 Solutions February 28, 2005

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 by contradiction. So suppose that m pigeons are placed into k pigeonholes, but no hole has more than ⌊\frac{m−1}{k}⌋ pigeons, or in other words, that the number of pigeons in each hole is

≤ ⌊\frac{m − 1}{k}⌋.

Counting the total number of pigeons in all k of the pigeonholes, we see that there can be at most:

k · ⌊\frac{m − 1}{k}⌋ ≤ k · \frac{m − 1}{k} = m − 1

of them. This is a contradiction because we said m pigeons were placed.

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 ≥ 1).

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 ⌊\frac{m−1}{52}⌋ = 3. The smallest m for which this is true is m = 3 × 52 + 1 = 157.

II. A) The answer here is the same as the number of 3-combinations of the multiset {∞ · a_{1}, …, ∞ · a_{150}} (where the 150 elements represent the 150 guests. This number is

\binom{3 + (150 − 1)}{(150 − 1)} = \binom{152}{149} = \binom{152}{3}

(Note: You can also derive this from scratch as follows. There are 150 = \binom{150}{1} ways for one person to win all three prizes; there are 2\binom{150}{2} for one person to get one prize and one to get two prizes. Finally there are \binom{150}{3} ways for three distinct people to get the prizes. Adding, we get

\binom{150}{1} + 2\binom{150}{2} + \binom{150}{3} = \binom{152}{3}

(by the Pascal’s Triangle identity, or Vandermonde convolution).

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.)

C) Answer is 150 · 149 · 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).

III. A) There are \binom{12}{5} ways to select 5 slips from the first 12. Similarly there are \binom{13}{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:

\binom{12}{5} · \binom{13}{3}

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} ≥ 0 (we might not have any slips in the first and fourth groups), and x_{2}, x_{3} ≥ 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 ≤ j ≤ 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} ≥ 0 are integers. As we know from examples in class the number of solutions in nonnegative integers of an equation of this type is

\binom{16 + (4 − 1)}{(4 − 1)} = \binom{19}{3}.

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}\binom{n}{k}. On the other hand, from the whole set of n cars, we can select any number 0 ≤ j ≤ 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:

∑_{j=0}^{k} \binom{n}{j}\binom{n − j}{k − j} = \binom{n}{0}\binom{n}{k} + \binom{n}{1}\binom{n − 1}{k − 1} + ⋯ + \binom{n}{k}\binom{n − k}{0}

The equality

∑_{j=0}^{k} \binom{n}{j}\binom{n − j}{k − j} = 2^{k}\binom{n}{k}

then follows because we are just counting the same set in two different ways.

V. We want to count the number of n-combinations of the multiset {n·a, 1·b_{1}, …, 1·b_{2n+1}}. Partition the collection of these n-combinations by the number of a’s that are included, and count the number of choices for the b_{i}’s in each case. There are

\binom{2n+1}{n} with no a’s
\binom{2n+1}{n−1} with exactly one a
⋮
\binom{2n+1}{n−j} with exactly j a’s
⋮
\binom{2n+1}{0} with n a’s

By the Addition Rule, the number of n-combinations is

∑_{j=0}^{n} \binom{2n + 1}{j}.

Now, notice that this is the “first half” of the sum of all the binomial coefficients \binom{2n+1}{j} (the second half are the ones with j = n + 1, …, 2n + 1). By the “symmetry relation” \binom{k}{ℓ} = \binom{k}{k−ℓ}, and the consequence ∑_{j=0}^{2n+1} \binom{2n+1}{j} = 2^{2n+1} of the Binomial Theorem, we have

2^{2n+1} = ∑_{j=0}^{2n+1} \binom{2n + 1}{j}

= ∑_{j=0}^{n} \binom{2n + 1}{j} + ∑_{j=n+1}^{2n+1} \binom{2n + 1}{j}

= ∑_{j=0}^{n} \binom{2n + 1}{j} + ∑_{j=n+1}^{2n+1} \binom{2n + 1}{2n + 1 − j}

= ∑_{j=0}^{n} \binom{2n + 1}{j} + ∑_{ℓ=0}^{n} \binom{2n + 1}{ℓ}

= 2 · ∑_{j=0}^{n} \binom{2n + 1}{j}

⇒ 2^{2n} = ∑_{j=0}^{n} \binom{2n + 1}{j}

(At the last step, we divided by 2 on both sides.) This is what we wanted to show.