AMC 10 · 2025 · #21

Grade 3 number-theory

Archetype Pair-Sum Invariant └ Sub-archetype Forbidden-Complement Selection

sum-free-setpair-countingparity extremal-construction ↑ Prerequisites: sum-free-set

📏 Long solution 💡 3 insights

Problem

Call a set sum-free if adding any two of its members (the two may be equal) never lands on a member of the set. Working only with whole numbers from 1 to 20, find the largest number of elements a sum-free subset can have.

Pick an answer.

(A)

(B)

(C)

(D)

(E)

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

How to solve

Strategy Extreme Principle

A 'greatest possible size' question is really two jobs (Tool #7): build one set that hits the target size, and prove nothing bigger can exist. The build is a quick guess-and-check (Tool #6). The proof is where Tool #14 (Extreme Principle) carries the weight: instead of arguing about the whole messy set, focus on its single largest element m. Fixing that extreme value forces strong structure on everything below it. The engine of that structure is complementary pairing (Tool #16): group the numbers under m into pairs {x, m-x} that add up to m; since m is in the set, no such pair can be fully inside. Listing those pairs (Tool #2) makes the count exact, and comparing the resulting cap against the answer choices (Tool #3) rules out 11 and 12.

1STEP 1

Build a sum-free set of size 10

Guess A={11,12,…,20}: the smallest sum 11+11=22 already passes 20, so no sum returns. A is sum-free with 10 elements.

A={11,12,…,20}, min-sum=11+11=22 ＞ 20 → |A|=10

2STEP 2

Focus on the largest element

Now the bound. In any sum-free A, let m be its largest element: every other element of A sits strictly below m, inside {1,2,…,m-1}.

m=max A, A∖{m}⊆{1,2,…,m-1}

3STEP 3

Pair numbers by what adds to m

Pair the numbers under m as x and m-x. Both cannot be in A, since x+(m-x)=m already is, so each pair hands over at most one element.

{x, m-x}: x+(m-x)=m∈ A forbidden → at most one of x, m-x in A

4STEP 4

Count the cap when m is odd

Odd m=2k-1: the numbers below split into exactly k-1 pairs, so |A| is at most (m+1)/2, and the largest odd m=19 gives 10.

m=2k-1: |A| ≤ (k-1)+1=(m+1)/2 ≤ (19+1)/2=10

5STEP 5

Count the cap when m is even

Even m=2k: the leftover middle k is banned too, since k+k=m is in A, so |A| is at most m/2, which is still 10.

m=2k: k+k=m∈ A bans k; |A| ≤ (k-1)+1=m/2 ≤ 20/2=10

6STEP 6

Combine and rule out 11 and 12

Both cases cap |A|, ruling out 11 and 12, and step 1 already reached the cap — so the greatest possible size is exactly 10, choice (C).

|A| ≤ 10 always, and 10 is achievable → max|A|=10 (C)

Answer

The bound |A| ≤ m/2 ≤ 10 is tight from both directions: the odd top m=19 gives the all-odds set {1,3,…,19} of size 10, and the even top m=20 gives {11,…,20} of size 10, matching the cap. The choices (8 to 12) cluster around half of 20, exactly what the pairing argument predicts, and the argument shows 11 and 12 are unreachable. Quick trap check: grabbing the small numbers {1,2,…} fails immediately since 1+2=3, so bigger-range does not mean bigger set — the ceiling is structural, not about how much room is left below 20.

💡Key takeaway

Look at the biggest number in the set: everything below it splits into pairs that add up to it, and each pair can lend only one member, so a sum-free set can hold at most half of 1 through 20 — ten numbers.

Build a sum-free set of size 10
Focus on the largest element
Pair numbers by what adds to m
Count the cap when m is odd
Count the cap when m is even
Combine and rule out 11 and 12