2012 AMC 10A Problem 23

Draw the six people as dots and each friendship as a line between two dots. Everyone has the same number of friends; call it $k$.

1. Possible values of $k$. "Some" are friends, so $k \ge 1$. Each person has only $5$ others to be friends with, and "not all" rules out $k = 5$. So $k$ is $1$, $2$, $3$ or $4$.
2. A shortcut. Swap every line for a non-line and every non-line for a line. Someone with $k$ friends now has $5 - k$ friends. Swapping twice gets back to the start, so the $k = 1$ setups match up one-for-one with the $k = 4$ setups, and $k = 2$ matches $k = 3$. So we only need to count $k = 1$ and $k = 2$.
3. $k = 1$: everyone has exactly one friend. The six people split into three pairs. Adam's friend can be any of the other $5$. Among the $4$ people left, take the first one alphabetically; their friend can be any of the other $3$. The last two people must be friends. That gives $5 \times 3 = 15$ ways.
4. $k = 2$: everyone has exactly two friends. Start at one person and walk from friend to friend. You go around a closed loop. A loop needs at least $3$ people, so the six people form either one loop of six or two loops of three.
- One loop of six. Seat the six around a round table and make each person friends with their two neighbours. There are $6! = 720$ seatings, but turning the table ($6$ ways) or flipping it over ($2$ ways) gives the same friendships. That leaves $\frac{720}{12} = 60$ ways.
- Two loops of three. Choose Adam's two loop-mates: $\binom52 = 10$ ways. The other three form the second loop. That gives $10$ ways.
- Total for $k = 2$: $60 + 10 = 70$.
5. By the shortcut, $k = 3$ also gives $70$ and $k = 4$ also gives $15$.
6. Total: $15 + 70 + 70 + 15 = 170$.

The answer is $\boxed{\textbf{(B)}\ 170}$.

Swapping "friends" with "not friends" turns one case into another, so you only have to count half the cases. When everyone has exactly two friends, the friendships always form closed loops, which makes that case easy to list. When a problem looks the same after swapping yes and no, count the smaller half and use the match-up for the rest.

Count $k = 3$ directly to check the shortcut. With six people and three friends each, there are two shapes. First, two groups of three where everyone is friends with all of the other group: choose the groups in $\binom63 \div 2 = 10$ ways. Second, two triangles with each corner of one joined to one corner of the other, like the edges of a triangular prism: $6! \div 12 = 60$ ways. That is $70$, the same as $k = 2$.