Mathematics 357 – Combinatorics 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 = 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 ⌊\frac{m−1}{12}⌋ = 3. The smallest m for which this is true is m = 3 × 12 + 1 = 37.

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 · 99 · 98 = P (100, 3).

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 · 100 · 100 = 100^{3}

different assignments of prizes to guests.

C) Now, the prizes are 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!:

\frac{100 · 99 · 98}{3!} = \binom{100}{3}

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 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 {∞·a_{1}, …, ∞·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.

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

\binom{10}{6} · \binom{20}{4}

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}, …, x_{8}. We must have

x_{1} + x_{2} + ⋯ + x_{8} = 23,

where x_{1}, x_{8} ≥ 0 (we might not have any slips in the first and eighth groups), and x_{2}, x_{3}, ⋯, x_{7} ≥ 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 ≤ j ≤ 7, and y_{8} = x_{8}, this means we need to count the number of solutions of

y_{1} + y_{2} + ⋯ + y_{8} = 11

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{11 + (8 − 1)}{(8 − 1)} = \binom{18}{7}.

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

∑_{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.