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

Directions

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. Relax, and read each question carefully before starting to work!

I. A) (15) Show that if m “pigeons” are placed into k “pigeonholes,” then some hole contains

more than ⌊\frac{m−1}{k}⌋ pigeons. (Here ⌊x⌋ is the greatest integer ≤ x.) B) (10) What is the smallest number of people for which it is 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.)

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:

A) (8.\overline{3}) All three prizes are $20 and after each winning number is drawn, it is replaced

in the pool of potential winners. B) (8.\overline{3}) The prizes are $50, $25, $10, and after each winning number is drawn, it is

replaced in the pool of potential winners. 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 is not replaced in the pool of potential winners.

III. Slips of paper numbered 1 to 25 are arranged side by side on a table.

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? 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?

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:

\binom{n}{0}\binom{n}{k} + \binom{n}{1}\binom{n − 1}{k − 1} + ⋯ + \binom{n}{k}\binom{n − k}{0} = 2^{k}\binom{n}{k}

V. (25) Show that there are 2^{2n} different n-combinations of the multiset

{n · a, 1 · b_{1}, …, 1 · b_{2n+1}}.