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$.

Picture the six people as points and each friendship as a segment between two points. Every person has the same number $k$ of friends. "Some" friendships means $k \ge 1$; "not all" rules out everyone being friends with everyone, so $k \le 4$.

Complement symmetry: if we swap every friendship for a non-friendship and vice versa, a configuration in which everyone has $k$ friends becomes one in which everyone has $5 - k$ friends, and swapping back undoes it. So there are as many $k = 3$ configurations as $k = 2$, and as many $k = 4$ as $k = 1$. Only $k = 1$ and $k = 2$ need to be counted.

$k = 1$: the six people split into three friend pairs. Adam's friend can be any of $5$ people; the first person not yet paired has $3$ choices; the last pair is forced. That is $5 \cdot 3 = 15$.

$k = 2$: each person's two friendships link into closed loops that cover all six people, and a loop needs at least three people, so the loops are either one loop of six or two loops of three.

• One loop of six: seat six people around a circle, $\frac{5!}{2} = 60$ ways, because rotating or reflecting the circle gives the same friendships.
• Two loops of three: choose Adam's two loop-mates in $\binom{5}{2} = 10$ ways; the other three form the second loop.

So $k = 2$ gives $70$, hence $k = 3$ gives $70$ and $k = 4$ gives $15$. Total: $15 + 70 + 70 + 15 = 170$.

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