2012 AMC 10A 第 23 题

先试着解答 2012 AMC 10A 第 23 题,然后核对你的答案与精心整理的解答,解答来自 LIVE by Po-Shen Loh。你也可以参加完整限时模拟考试、查看全部 2012 AMC 10A 解答,或核对答案

所有题目均经美国数学协会(MAA)官方合法授权使用。

23.

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?

6060

170170

290290

320320

660660

答案:B
知识点:图论分类讨论双射
难度评级:2200
解答:

按每个人拥有的好友数分类。由于好友图既不是空图也不是完全图,这个数从 1144

注意,11 个好友和 22 个好友的情况,分别通过取补图与 44 个好友和 33 个好友的情况对应,因为确定谁是好友也就确定了谁不是好友。

情况一:每个人有 11 个好友

这意味着 66 个人必须分成 33 对,每对中的两人互为好友。

第一个人的好友有 55 种选择,剩下 44 个人。

下一位未配对者的好友有 33 种选择,剩余的 22 个人则必须互为好友。

因此这种情况共有 35=153 \cdot 5 = 15 种可能。

情况二:每个人有 22 个好友

这种情况有两种可能。第一种是分成两个三人组,每组三人彼此都是好友。

选择第一个三人组有 (63)=20\binom{6}{3} = 20 种方法。由于两个组可以互换,必须除以 22,得到 20÷2=1020 \div 2 = 10 种配置。

第二种可能是好友关系形成一个 66 环。

六个人沿环的每一种排列都给出这样的图。选择起点会使每个图被计算 66 次,选择遍历方向又会被计算 22 次,因此不同的 66 环共有 6!/(62)=606!/(6\cdot2)=60 个。再加上 1010 个两三角形配置,本情况共有 10+60=7010+60=70 种配置。

所以总配置数为 2(15+70)=170. 2(15 + 70) = 170.

所以正确答案是 B

We case on the value of friends that each person has. This value ranges from 11 to 44, since the graph is neither empty nor complete.

Note that the cases for 11 and 22 friends correspond with the case for 44 and 33 friends, since choosing who are friends determines who are not friends.

Case 1: everyone has 11 friend

This means that the 66 people must split up into 33 pairs where the people in each pair are friends.

There are 55 choices for the friend for the first person. This leaves 44 people remaining.

There are then 33 choices for the friend of the next unpaired person. The remaining 22 people are then forced to be friends.

Therefore, there are 35=153 \cdot 5 = 15 possibilities for this case.

Case 2: everyone has 22 friends

There are two possibilities for this case. There could be two triples where everyone in a triple is friends with each other.

For this possibility, there are (63)=20\binom{6}{3} = 20 ways to choose the people in the first triple. We have to divide by 22 since we can swap the pairs. This gives us 20÷2=1020 \div 2 = 10 configurations.

The second possibility is that the friends form one 66-cycle.

Every ordering of the six people around a cycle gives such a graph. Each graph is counted 66 times by the choice of starting person and 22 times by the direction of traversal, so there are 6!/(62)=606!/(6\cdot2)=60 distinct 66-cycles. Together with the 1010 pairs of triangles, this case has 10+60=7010+60=70 configurations.

The total number of arrangements is then 2(15+70)=170. 2(15 + 70) = 170.

Thus, B is the correct answer.

← 第 22 题#22
完整试卷

其他年份的第 23 题