HMMT 二月 2006 · GEN1 赛 · 第 6 题
HMMT February 2006 — GEN1 Round — Problem 6
题目详情
- Six 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?
解析
- Six 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: 70 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. Either there is one big circle of all 6 celebrities or else there are two small circles of 3 celebrities each. If there is one big circle of 6, then depending on the ordering of the people in the circle, the fan’s list can still vary. Literally speaking, there are 5! different circles 6 people can make: fix one of the people, and then there are 5 choices for the person to the right, 4 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. There are thus 5! / 2 = 60 different possible lists here. ( ) 6 If there are two small circles of 3, then there are different ways the members of 3 the “first” small circle may be selected. But this, too, is double-counting, because it makes no difference which circle is termed the “first” and which the “second.” There ( ) 6 are therefore / 2 = 10 essentially different ways to split up the people into the two 3 circles. In a circle of just three, each person shakes hands with both the others, so naturally the order of people in the circle doesn’t matter. There are thus 10 different possible lists here. (Note that, translated into the language of graph theory, the problem is asking for the number of graphs on six labeled vertices such that each vertex has degree two.)