AMC 10 · 2025 · #15

Grade 7 counting

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

sum-free-setpair-countingparity extremal-constructioncasework ↑ Prerequisites: pair-counting

📏 Medium solution 💡 3 insights

Problem

From the numbers 1 through 20 we choose a subset A. The subset is called sum-free when no two chosen numbers ever add up to another chosen number: whenever x and y are in A (they may be the same number), the sum x + y is not in A. We want the largest number of elements such a sum-free subset can have.

Pick an answer.

(A)

(B)

(C)

(D)

(E)

How to solve

Strategy Extreme Principle

A largest-possible-size question has two halves: build a set that is actually that big (a lower bound) and prove nothing bigger can exist (an upper bound). Testing one well-chosen large set settles the lower bound quickly. For the ceiling, the winning move is the extreme principle: fix attention on the single largest element m of any sum-free set. Because m is the biggest number present, every way of writing m as x + (m - x) is a trap, so m forbids one member of each pair that adds up to it. Counting those pairs caps the size. Focusing on the extreme element turns an open-ended search into a clean count.

1STEP 1

Build a large sum-free set

The top half {11, …, 20} has ten members; even 11 + 11 = 22 exceeds 20, so no sum lands inside — a sum-free set of size 10 exists.

11 + 11 = 22 ＞ 20 → x + y ＞ 20 for all x, y ∈ {11, …, 20}

2STEP 2

Fix on the largest element

Let m be the largest element. For any x, its partner m - x can't also be in A, or x + (m - x) = m would equal a member.

x + (m - x) = m → x and m - x cannot both lie in A

3STEP 3

Pair up and count the ceiling

Pairing each x with m - x below m, every pair sums to m so at most one survives; with m at most 20, the count caps at 10.

m even: |A| ≤ m/2 ≤ 10; m odd: |A| ≤ (m+1)/2 ≤ 10

4STEP 4

Both halves meet at 10

Step 1 reaches 10 and Steps 2–3 forbid more, so the two bounds pin the maximum at exactly 10 — choice (C).

10 ≤ |A|_max ≤ 10 → |A|_max = 10

Answer

The bound is tight and self-consistent. The set {11, ..., 20} really does achieve 10, and the ten odd numbers {1, 3, 5, ..., 19} give a second size-10 witness, since odd + odd is always even and so can never equal an odd member. Meanwhile no set can reach 11: the largest element alone forces out at least one of each pair that sums to it, roughly half of the smaller numbers. So choices (D) 11 and (E) 12 exceed the proven ceiling, and 10 is the only value consistent with both the concrete example and the counting argument.

💡Key takeaway

To find the biggest set with no two members adding to a third, look at the largest element: it blocks one number from every pair that adds up to it, so about half the smaller numbers must be left out.

Build a large sum-free set
Fix on the largest element
Pair up and count the ceiling
Both halves meet at 10

Build a large sum-free set

Fix on the largest element

Pair up and count the ceiling

Both halves meet at 10

More like this