AMC 10 · 2012 · #23
Grade 7 countingAdam, 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?
Pick an answer.
AMC 10 2012 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.
Try it yourself first — the explanation is most useful after you’ve attempted it.
Toolkit + CCSS Solution
Understand
Restated: Six people can be internet friends with each other. Friendship is mutual: if you are my friend, I am yours. Not everyone is friends with everyone, and no one is friendless-outside the group. The one rule that ties them together is that every single person has the exact same number of friends. Count how many different friendship setups make that true.
Givens: There are exactly $6$ people: Adam, Benin, Chiang, Deshawn, Esther, Fiona; Friendship is mutual (an unordered pair); Every person has the same number of friends; "Some, but not all" pairs are friends — so at least one friendship exists, but not every possible pair is a friendship; Answer choices: (A) $60$, (B) $170$, (C) $290$, (D) $320$, (E) $660$
Unknowns: The number of distinct friendship setups (who-is-friends-with-whom) meeting all the conditions
Understand
Restated: Six people can be internet friends with each other. Friendship is mutual: if you are my friend, I am yours. Not everyone is friends with everyone, and no one is friendless-outside the group. The one rule that ties them together is that every single person has the exact same number of friends. Count how many different friendship setups make that true.
Givens: There are exactly $6$ people: Adam, Benin, Chiang, Deshawn, Esther, Fiona; Friendship is mutual (an unordered pair); Every person has the same number of friends; "Some, but not all" pairs are friends — so at least one friendship exists, but not every possible pair is a friendship; Answer choices: (A) $60$, (B) $170$, (C) $290$, (D) $320$, (E) $660$
Plan
Primary tool: #2 Make a Systematic List
Secondary: #16 Change Focus / Count the Complement, #1 Draw a Diagram, #4 Introduce a Variable, #7 Identify Subproblems
This is a "how many ways" count, so Tool #2 (Make a Systematic List) is the spine: split the count by $k$, the shared friend-count, and enumerate each case cleanly. First Tool #4 (Introduce a Variable) names $k$ and pins it to $\{1,2,3,4\}$. Then Tool #16 (Count the Complement) does the heavy lifting: flipping every friendship to a non-friendship turns a $k$-friend setup into a $(5-k)$-friend setup, so the $k=1$ count equals the $k=4$ count and the $k=2$ count equals the $k=3$ count — cutting the work in half. Tool #1 (Draw a Diagram) makes the $k=2$ shapes (triangles and a hexagon) visible so nothing is missed or double-counted. Tool #7 (Identify Subproblems) keeps the finish tidy: count $k=1$, count $k=2$, then double and add.
Execute — Answer: B
6.EE.A.2 Step 1 Name the shared friend count
- Draw the six people as six dots; a friendship is a line joining two dots.
- "Everyone has the same number of friends" means every dot has the same number of lines coming out of it.
- Call that shared number $k$.
- A person can be friends with at most the other $5$ people.
- The problem says some pairs are friends (so $k\neq 0$) but not all pairs are friends (so $k\neq 5$).
- That leaves exactly four possibilities.
💡 Giving the common friend-count a single name $k$ turns a fuzzy condition into four clean cases to count.
7.SP.C.8 Step 2 Flip friendships to pair the cases
- Take any valid setup and flip it: every pair that were friends become strangers, and every pair that were strangers become friends.
- A person who had $k$ friends was a stranger to $5-k$ people, so after the flip that person has $5-k$ friends — and this is still a valid "everyone equal" setup.
- Flipping is reversible, so it matches setups one-to-one.
- That means the number of $k=1$ setups equals the number of $k=4$ setups, and the number of $k=2$ setups equals the number of $k=3$ setups.
- So I only need to count $k=1$ and $k=2$, then double each.
💡 Swapping "friend" and "stranger" trades $k$ for $5-k$ without losing the equal-count property, so the hard half mirrors the easy half.
3.OA.C.7 Step 3 Count k = 1: split into three pairs
- If everyone has exactly $1$ friend, the six people break into $3$ separate friend-pairs with no other lines.
- Count the pairings systematically.
- Adam has $5$ choices for his one friend.
- Now look at the lowest-labeled person still unpaired: they have $3$ choices left.
- The final two people are forced to be each other's friend: $1$ way.
- Multiply the independent choices.
💡 Pick a partner for one person at a time; each choice is independent, so the counts just multiply.
7.SP.C.8 Step 4 Count k = 2, shape one: two triangles
- If everyone has exactly $2$ friends, each dot has two lines, so the lines form closed loops that use every dot.
- With six dots the loops can be two triangles (two loops of $3$) or one big loop of $6$; a loop of length $1$ or $2$ is impossible.
- Handle two triangles first.
- Splitting six people into two groups of three, where each group is a mutual-friend triangle, means choosing which three people form one triangle — the other three are forced.
- Choosing $3$ of $6$ is $\binom{6}{3}=20$ ways, but that counts each split twice (picking group $A$ or picking group $B$ gives the same split), so divide by $2$.
💡 A triangle is the only 2-friend shape for a group of three, so you just choose who is in one triangle — and each split is named twice.
4.OA.A.3 Step 5 Count k = 2, shape two: one hexagon
- The other degree-$2$ shape is a single loop through all six people — a hexagon, where each person is friends with their two neighbors around the ring.
- Count the rings: line the six people up around a circle in $6! = 720$ orders.
- But the same ring of friendships is counted many times: rotating the circle to any of $6$ starting spots gives the same friendships, and reading the circle clockwise or counterclockwise ($2$ directions) also gives the same friendships.
- Divide out these repeats.
- Add the two shapes to get the full $k=2$ count.
💡 A ring of friendships doesn't care where you start reading it or which way you go, so those $6\times 2$ look-alikes collapse to one.
4.OA.A.3 Step 6 Double each case and add
- By the flip in step 2, $k=4$ has the same count as $k=1$ and $k=3$ has the same count as $k=2$.
- So the four cases together are $N_1 + N_2 + N_3 + N_4 = 2N_1 + 2N_2$.
- Plug in $N_1 = 15$ and $N_2 = 70$.
💡 The complement pairing means you compute only two cases and mirror them, so the grand total is just twice their sum.
6.EE.A.2 Draw the six people as six dots; a friendship is a line joining two dots. "Every 7.SP.C.8 Take any valid setup and flip it: every pair that were friends become strangers, 3.OA.C.7 If everyone has exactly $1$ friend, the six people break into $3$ separate frien 7.SP.C.8 If everyone has exactly $2$ friends, each dot has two lines, so the lines form c 4.OA.A.3 The other degree-$2$ shape is a single loop through all six people — a hexagon, 4.OA.A.3 By the flip in step 2, $k=4$ has the same count as $k=1$ and $k=3$ has the same Review
Reasonableness: The total $170$ sits between choices $60$ and $290$, and it is not any raw sub-count, so a careless single-case answer wouldn't land on it. Cross-check the sub-counts: $k=1$ gives $15$ perfect pairings, which matches the double-factorial $5!! = 5\cdot 3\cdot 1 = 15$. For $k=2$, the number of $6$-cycles on labeled vertices is the known $\frac{(6-1)!}{2} = \frac{120}{2} = 60$, matching the hexagon count, and two-triangle splits give $10$, so $N_2 = 70$. Doubling and adding, $2(15+70) = 170$. The complement symmetry is also self-consistent: the four case counts are $15, 70, 70, 15$, which are symmetric about the middle exactly as flipping friends and strangers predicts.
Alternative: Instead of the complement shortcut, count all four cases directly. $k=1$ gives $15$ and $k=2$ gives $70$ as above. For $k=4$, each person is a stranger to exactly $1$ other person, so the "stranger" lines form $3$ pairs — the same count as $k=1$, namely $15$. For $k=3$, each person is a stranger to exactly $2$ others, so the stranger lines form triangles or a hexagon — the same count as $k=2$, namely $70$. Summing $15+70+70+15 = 170$ confirms the answer without relying on the symmetry argument, and shows why the flip works.
CCSS standards used (min grade 7)
6.EE.A.2Write, read, and evaluate expressions in which letters stand for numbers (Naming the shared friend count $k$ and using the conditions to restrict it to $\{1,2,3,4\}$.)7.SP.C.8Find probabilities of compound events using organized lists, tables, and simulations (Organizing the count by cases, using the friend/stranger flip to pair $k$ with $5-k$, and enumerating the two-triangle configurations.)3.OA.C.7Fluently multiply and divide within 100 (Multiplying the independent partner choices $5\times 3\times 1 = 15$ for the $k=1$ pairings.)4.OA.A.3Solve multi-step word problems using the four operations with whole numbers (Dividing out the rotations and reflections for the hexagon count $\frac{720}{12}=60$, then doubling and adding the cases to reach $170$.)
⭐ When everyone must have the same number of friends, sort by that shared number $k$; then notice that swapping "friend" and "stranger" turns $k$ friends into $5-k$ friends, so you only count half the cases and double them: $2(15+70)=170$.
⭐ When everyone must have the same number of friends, sort by that shared number $k$; then notice that swapping "friend" and "stranger" turns $k$ friends into $5-k$ friends, so you only count half the cases and double them: $2(15+70)=170$.
More like this
Same archetype — closest grade level first.
