2020 AMC 12B 第 15 题

Question

10

个人等间隔地站成一圈。每个人恰好认识其他

9

个人中的

3

个：站在其两侧的

2

个人，以及正对面的人。将这

10

个人分成

5

对，且每对的两人互相认识，一共有多少种分法？

There are

10

people standing equally spaced around a circle. Each person knows exactly

3

of the other

9

people: the

2

people standing next to her or him, as well as the person directly across the circle. How many ways are there for the

10

people to split up into

5

pairs so that the members of each pair know each other?

11

12

13

14

15

答案：C

知识点：图论分类讨论

难度评级：1730

小提示：

把允许的配对看作边：相邻边或直径边，然后数完美匹配。

Count perfect matchings using edges that are either adjacent (neighbor) pairs or diameters (across)

大提示：

按使用了多少条直径边分类；可能的数量只有

0, 1, 3

或

5

。

Organize by how many diameter pairs are used; only

0, 1, 3,

or

5

of them can occur

解答：

将人编号为

0

到

9

。允许的配对是相邻边

(i, i + 1)

或直径边

(i, i + 5)

。我们按使用的直径边数量分类计算完美匹配。

不使用直径边时，相邻的人可以按两种交错方式配对，共有

2

种。恰用一条直径边时，选择这条直径有

5

种，其余的人随后被唯一配对，因此共有

5

种。使用全部五条直径边时有

1

种。

只要使用了直径边，沿圆周考察被迫出现的相邻配对，就可看出直径边数必须是奇数。恰用三条直径边时，余下四人必须组成两对彼此对置的相邻配对；其中一对的位置唯一确定整个匹配，所以有

5

种。综上，总数为

2+5+5+1=13

。

所以正确答案是 C。

Label the people

0

through

9.

Allowed pairings use neighbor edges

(i, i + 1)

or diameter edges

(i, i + 5).

Count perfect matchings by the number of diameter edges used.

Using no diameters, the ten people split into adjacent pairs in

2

ways (all “even” edges or all “odd” edges). Using exactly one diameter, choose it in

5

ways; the remaining two arcs of four people each pair up uniquely, giving

5.

Using all five diameters gives

1

matching.

If at least one diameter is used, following the forced adjacent pairings around the circle shows that the number of diameters must be odd. With exactly three diameters, the four remaining people must be two opposite adjacent pairs. The position of one such opposite pair determines the matching, giving

5

possibilities. Hence the total is

2+5+5+1=13.

Thus, the correct answer is C.

2020 AMC 12B 第 15 题

答案：C

难度评级：1730

小提示：

大提示：

解答：

其他年份的第 15 题