HMMT 二月 2006 · COMB 赛 · 第 5 题

HMMT February 2006 — COMB Round — Problem 5

Fifteen freshmen are sitting in a circle around a table, but the course assistant (who remains standing) has made only six copies of today’s handout. No freshman should get more than one handout, and any freshman who does not get one should be able to read a neighbor’s. If the freshmen are distinguishable but the handouts are not, how many ways are there to distribute the six handouts subject to the above conditions?

解析

Fifteen freshmen are sitting in a circle around a table, but the course assistant (who remains standing) has made only six copies of today’s handout. No freshman should get more than one handout, and any freshman who does not get one should be able to read a neighbor’s. If the freshmen are distinguishable but the handouts are not, how many ways are there to distribute the six handouts subject to the above conditions? Answer: 125 Solution: Suppose that you are one of the freshmen; then there’s a 6 / 15 chance that you’ll get one of the handouts. We may ask, given that you do get a handout, how many ways are there to distribute the rest? We need only multiply the answer to that question by 15 / 6 to answer the original question. Going clockwise around the table from you, one might write down the sizes of the gaps between people with handouts. There are six such gaps, each of size 0–2, and the sum of their sizes must be 15 − 6 = 11. So the gap sizes are either 1, 1, 1, 2, 2, 2 in some 6! order, or 0, 1, 2, 2, 2, 2 in some order. In the former case, = 20 orders are possible; 3!3! 6! in the latter, = 30 are. Altogether, then, there are 20 + 30 = 50 possibilities. 1!1!4! Multiplying this by 15 / 6, or 5 / 2, gives 125.