AMC 10 · 2012 · #19

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

Six people pair off mutually and every one of them has the same number of partners. Count the setups.

Pick an answer.

(A)

(B)

170

(C)

290

(D)

320

(E)

660

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

The shared count runs over just four values.

k ∈ {1, 2, 3, 4}

2STEP 2

Flip friendships to pair the cases

Flipping the relation pairs the cases up.

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

3STEP 3

Count k = 1: split into three pairs

One partner each splits them into three couples.

N₁ = 5 × 3 × 1 = 15

4STEP 4

Count k = 2, shape one: two triangles

Two partners each allows two shapes.

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

5STEP 5

Count k = 2, shape two: one hexagon

The ring shape is the bigger count.

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

6STEP 6

Double each case and add

Doubling and adding gives 170, choice (B).

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