Bunuel
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?
(A) 60
(B) 170
(C) 290
(D) 320
(E) 660
We see that each of them can have at least 1 friend and at most 4 friends (that is because not all of them are friends).
Case 1: Each person has exactly 1 friend
If each person has exactly 1 friend, then we need to divide the 6 people into 3 groups of 2, and the number of ways we can do that is:
(6C2 x 4C2 x 2C2)/3! = (15 x 6 x 1)/6 = 15
Case 2: Each person has exactly 2 friends
If each person has 2 friends, then we have two options, with one option being the 6 people split into 2 groups of 3. The number of ways we can do that is:
(6C3 x 3C3)/2! = (20 x 1)/2 = 10
The other option is that the group can also form a friendship hexagon, with each person sitting on a vertex, and each side representing the two friends that person has. The first person may be seated anywhere on the hexagon. This person has 5C2 = 10 choices for the two friends on the adjoining vertices. Each of the three remaining people can be seated across from one of the original three people, forming a different configuration. Thus, there are 10 x 3! = 60 hexagonal configurations.
So case 2 has a total of 10 + 60 = 70 ways.
Case 3: Each person has exactly 3 friends
If each person has exactly 2 friends, then he/she has 3 non-friends. Now we can reverse it and argue that if each person has exactly 3 friends, then he/she has 2 non-friends. That is, there is a one-to-one correspondence between case 2 and case 3. So case 3 has 70 ways, just like in case 2.
Case 4: Each person has exactly 4 friends
Similarly to case 3, we can argue that if each person has exactly 1 friend, then he/she has 4 non-friends, and if each person has exactly 4 friends, then he/she has 1 non-friend. So case 4 has 15 ways, just like in case 1.
Therefore, the total number of ways each person has the same number of friends is 15 + 70 + 70 + 15 = 170.
Answer: B