AMC 8 · 2003 · #18

Grade 4 counting

Archetype Overlap / Complement Counting └ Sub-archetype Complement by Subtracting Forbidden Arrangements

systematic-enumerationcomplementary-countingset-partitionlogical-deduction complementary-countingsystematic-enumerationcasework ↑ Prerequisites: systematic-enumerationlogical-deduction

📏 Medium solution 💡 3 insights 📊 Diagram

📘 View easy version →

Problem

A graph shows 20 dots, each representing one of Sarah's classmates, with line segments connecting pairs of classmates who are friends. The central oval labeled "Sarah" is connected to her friends. Sarah's guest list consists of (i) every classmate directly connected to her (her friends) and (ii) every classmate connected to one of those friends (friends of friends). How many of the 20 classmates are not invited?

Pick an answer.

(A)

(B)

(C)

(D)

(E)

AMC 8 2003 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

How to solve

Strategy Draw a Diagram

The picture is the problem, so Tool #1 (Draw a Diagram) does the heavy lifting: label each dot with its shortest-edge distance from Sarah (1, 2, 3, or ∞ if disconnected). Tool #7 (Identify Subproblems) then splits "not invited" into two clean buckets: dots in a different piece of the graph from Sarah, and dots inside Sarah's piece but too far away (distance ≥ 3). Tool #16 (Complement) gives a fast cross-check: instead of recounting the not-invited at the end, we can also verify by counting the invited (distance 1 and 2) and subtracting from 20. Both routes must give the same answer.

1STEP 1

Label every dot with its distance from Sarah: she connects directly to 8 dots, so those are the distance-1 friends.

distance 1: {p,o,d,e,j,k,q,s}, |·|=8

2STEP 2

Step one edge further from each friend to the friends-of-friends: that distance-2 set holds 6 dots, all invited.

distance 2: {b,c,f,r,t,i}, |·|=6

3STEP 3

Split "not invited" into two disjoint buckets: A, dots with no path to Sarah; B, dots in her component at distance 3 or more.

not invited = A ∪ B, A ∩ B = ∅

4STEP 4

Bucket A (disconnected): the lower-left triangle l-m-n is 3 dots and the lone dot a is 1, so |A| = 4.

|A| = 3 + 1 = 4

5STEP 5

Bucket B (too far): along the chain e-f-g-h-i-j, the middle dots g and h sit at distance 3, so |B| = 2.

|B| = |{g,h}| = 2

6STEP 6

Add the disjoint buckets: 4 + 2 = 6, choice (D).

|A| + |B| = 4 + 2 = 6 → (D)

7STEP 7

Complement check: 8 + 6 = 14 invited, so 20 - 14 = 6 are uninvited — same answer.

20 - (8 + 6) = 20 - 14 = 6

Answer

Two independent counts agree on 6: direct counting of the not-invited (4 disconnected + 2 at distance 3) and the complement count (20 - 14 invited = 6). Sanity-check the buckets: 8 + 6 + 4 + 2 = 20, accounting for every dot exactly once. The answer must be at least 4 because the disconnected pieces alone contribute 4, ruling out (A) 1; it must be less than the total number of dots minus Sarah's 8 direct friends, ruling out the larger choices unless many friends-of-friends miss as well, which the picture shows is not the case. The middle option 6 is exactly right, matching choice (D).

💡Key takeaway

Label every dot with how many steps it is from Sarah, then sort: distance 1 and 2 get invited, everything else does not — this AMC 8 graph puzzle becomes a Grade 4 sort-and-add exercise giving 6.

More like this