2012 AMC 12A 第 19 题

Question

Adam、Benin、Chiang、Deshawn、Esther 和 Fiona 都有网络账户。他们中有一些人互为网络好友，但并非所有人都互为好友，并且他们没有这个小组之外的网络好友。每个人拥有相同数量的网络好友。这种情况有多少种不同的可能？

Adam, Benin, Chiang, Deshawn, Esther, and Fiona have internet accounts. Some, but not all, of them are internet friends with each other, and none of them has an internet friend outside this group. Each of them has the same number of internet friends. In how many different ways can this happen?

60

170

290

320

660

答案：B

知识点：图论补集计数分类讨论

难度评级：2090

小提示：

将好友关系建模为

6

个顶点的图，每个人的度数都是

n

，且

1 \le n \le 4

Model the friendships as a graph on

6

vertices where everyone has the same degree

n,

with

1 \le n \le 4

大提示：

情况

n = 1

和

n = 4

互为补图，

n = 2

和

n = 3

也互为补图；分别计数两种

2

-正则图类型

The cases

n = 1

and

n = 4

are complements of each other, as are

n = 2

and

n = 3;

count the two

2

-regular graph types separately

解答：

将人建模为图的顶点，好友关系为边。每个人的度数相同，设为

n

，其中

1 \le n \le 4

。度数为

n

和

6 - 1 - n

的图互为补图，所以

n = 1

与

n = 4

配对，

n = 2

与

n = 3

配对。

当

n = 1

时，图是完美匹配：有

5 \cdot 3 = 15

种。因此

n = 4

也有

15

种。

当

n = 2

时，图是若干个圈的并：要么是两个三角形

\left(\binom{5}{2} = 10\right)

，要么是一个六边形

\left(\dfrac{6!}{12} = 60\right)

，总计

70

种。因此

n = 3

也有

70

种。

总数为

15 + 15 + 70 + 70 = 170

。

因此，正确答案是 B。

Model people as vertices of a graph, with edges for friendships. Everyone has the same degree

n

with

1 \le n \le 4.

The cases

n

and

6 - 1 - n

are complementary graphs, so

n = 1

pairs with

n = 4

and

n = 2

with

n = 3.

For

n = 1

the graph is a perfect matching:

5 \cdot 3 = 15

ways. Thus

n = 4

also gives

15.

For

n = 2

the graph is a union of cycles: either two triangles

\left(\binom{5}{2} = 10\right)

or one hexagon

\left(\dfrac{6!}{12} = 60\right),

totaling

70.

Thus

n = 3

also gives

70.

The total is

15 + 15 + 70 + 70 = 170.

Thus, the correct answer is B.

2012 AMC 12A 第 19 题

答案：B

难度评级：2090

小提示：

大提示：

解答：

其他年份的第 19 题