Question

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$

Answer: B

Concepts:graph theory complementary counting casework

Difficulty rating: 2090

Solution:

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 Problem 19

Answer: B

Difficulty rating: 2090

Solution:

Problem 19 in Other Years