2012 AMC 10A Problem 23

Attempt Problem 23 of the 2012 AMC 10A below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2012 AMC 10A solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

23.

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

Answer: B
Concepts:graph theorycaseworkbijection
Difficulty rating: 2200
Solution:

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.

← Problem 22#22
Full Exam

Problem 23 in Other Years