HMMT 二月 2006 · COMB 赛 · 第 9 题
HMMT February 2006 — COMB Round — Problem 9
题目详情
- Eight celebrities meet at a party. It so happens that each celebrity shakes hands with exactly two others. A fan makes a list of all unordered pairs of celebrities who shook hands with each other. If order does not matter, how many different lists are possible?
解析
- Eight celebrities meet at a party. It so happens that each celebrity shakes hands with exactly two others. A fan makes a list of all unordered pairs of celebrities who shook hands with each other. If order does not matter, how many different lists are possible? Answer: 3507 Solution: Let the celebrities get into one or more circles so that each circle has at least three celebrities, and each celebrity shook hands precisely with his or her neighbors in the circle. Let’s consider the possible circle sizes: • There’s one big circle with all 8 celebrities. Depending on the ordering of the people in the circle, the fan’s list can still vary. Literally speaking, there are 7! different circles 8 people can make: fix one of the people, and then there are 7 choices for the person to the right, 6 for the person after that, and so on. But this would be double-counting because, as far as the fan’s list goes, it makes no difference if we “reverse” the order of all the people. Thus, there are 7! / 2 = 2520 different possible lists here. ( ) 8 4! • 5+3. In this case there are ways to split into the two circles, essentially 5 2 2! different ways of ordering the 5-circle, and ways for the 3-circle, giving a total 2 count of 56 · 12 · 1 = 672. ( ) 8 • 4+4. In this case there are / 2 = 35 ways to split into the two circles (we divide 4 by 2 because here, unlike in the 5 + 3 case, it does not matter which circle is 3! which), and = 3 ways of ordering each, giving a total count of 35 · 3 · 3 = 315. 2 Adding them up, we get 2520 + 672 + 315 = 3507 .