2012 AMC 10A Problem 23

Below is the professionally curated solution for Problem 23 of the 2012 AMC 10A, 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 of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:graph theorycaseworkbijection

Difficulty rating: 2200

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

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 if the friends form a hexagon where the person at each vertex is friends with the adjacent people.

The first person can be placed anywhere on the hexagon. There are (52)=10\binom{5}{2} = 10 ways to choose the people adjacent to this person.

The final 33 people can be placed in 3!=63! = 6 ways in the remaining spots. This case then has a total number of 10+106=70 10 + 10 \cdot 6 = 70 configurations.

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

Thus, B is the correct answer.

Problem 23 in Other Years