AMC 10 · 2012 · #23

Grade 7 countinglogic

Archetype Casework by Position / Vertex Type └ Sub-archetype Count of Type

systematic-enumerationcombinations-basiccomplementary-counting caseworkcomplementary-counting ↑ Prerequisites: combinations-basic

📏 Long solution 💡 4 insights

Problem

Adam, Benin, Chiang, Deshawn, Esther, and Fiona have internet accounts. Friendship is mutual: if I am your friend, you are mine. 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.

(A)

(B)

170

(C)

290

(D)

320

(E)

660

AMC 10 2012 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

How to solve

Strategy Make a Systematic List

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.

1STEP 1

Name the shared friend count

Draw six dots and a line per friendship. Every dot has the same number of lines — call it k. Not 0, not 5, so k is 1, 2, 3, or 4.

k ∈ {1, 2, 3, 4}

2STEP 2

Flip friendships to pair the cases

Swap friend and stranger: k friends become 5-k friends, so k=1 mirrors k=4 and k=2 mirrors k=3 — count only two cases.

N₁ = N₄, N₂ = N₃ → Total = 2N₁ + 2N₂

3STEP 3

Count k = 1: split into three pairs

With one friend each, the six split into three pairs: Adam picks from 5, the next unpaired person from 3, the last two are forced — 15.

N₁ = 5 × 3 × 1 = 15

4STEP 4

Count k = 2, shape one: two triangles

With two friends each the lines close into loops: two triangles or one hexagon. Two triangles means choosing 3 of 6, halved — 10.

(C(6, 3))/2 = 20/2 = 10

5STEP 5

Count k = 2, shape two: one hexagon

The hexagon: seat all six in a ring, 720 orders, but 6 rotations and 2 directions repeat each ring — 60 rings, so k=2 gives 70.

6!/(6 × 2) = 720/12 = 60, N₂ = 10 + 60 = 70

6STEP 6

Double each case and add

k=4 matches k=1 and k=3 matches k=2, so the total is 2(15) + 2(70) = 170.

2(15) + 2(70) = 30 + 140 = 170 → (B)

Answer

170

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 · 3 · 1 = 15. For k=2, the number of 6-cycles on labeled vertices is the known ((6-1)!)/2 = 120/2 = 60, matching the hexagon count, and two-triangle splits give 10, so N₂ = 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.

💡Key takeaway

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.

Name the shared friend count
Flip friendships to pair the cases
Count k = 1: split into three pairs
Count k = 2, shape one: two triangles
Count k = 2, shape two: one hexagon
Double each case and add