Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2012 AMC 10A Problems/Problem 23

Revision as of 01:12, 9 February 2012 by Talkinaway (talk | contribs) (!)

Problem 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?

$\textbf{(A)}\ 60\qquad\textbf{(B)}\ 170\qquad\textbf{(C)}\ 290\qquad\textbf{(D)}\ 320\qquad\textbf{(E)}\ 660$

Solution

Note that if $n$ is the number of friends each person has, then $n$ can be any integer from $1$ to $4$, inclusive.

Also note that the cases of $n=1$ and $n=4$ are the same, since a map showing a solution for $n=1$ can correspond one-to-one with a map of a solution for $n=4$ by simply making every pair of friends non-friends and vice versa. The same can be said of configurations with $n=2$ when compared to configurations of $n=3$. Thus, we have two cases to examine, $n=1$ and $n=2$, and we count each of these combinations twice.

For $n=1$, if everyone has exactly one friend, that means there must be $3$ pairs of friends, with no other interconnections. The first person has $5$ choices for a friend. There are $4$ people left. The next person has $3$ choices for a friend. There are two people left, and these remaining two must be friends. Thus, there are $15$ configurations with $n=1$.

For $n=2$, there are two possibilities. The group of $6$ can be split into two groups of $3$, with each group creating a "friendship triangle." The first person has $\binom{5}{2} = 10$ ways to pick two friends from the other five, while the other three are forced together. Thus, there are $10$ triangular configurations.

However, the group can also from 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 WLOG. This person has $\binom{5}{2} = 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 \cdot 3! = 60$ hexagonal configurations, and in total $70$ configurations for $n=2$.

As stated before, $n=3$ has $70$ configurations, and $n=4$ has $15$ configurations. This gives a total of $(70 + 15)\cdot 2 = 170$ configurations, which is option $\textbf{(B)}$

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2012_AMC_10A_Problems/Problem_23&oldid=44619"