2012 AMC 12A Problem 19

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

Small hint:

Model the friendships as a graph on

6

vertices where everyone has the same degree

n,

with

1 \le n \le 4

Big hint:

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

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

Small hint:

Big hint:

Solution:

Problem 19 in other years