AMC 10 · 2022 · #14

Grade 6 arithmetic

Archetype Small-Domain Constrained Search └ Sub-archetype Logic-Deduction / Elimination

sum-free-setset-partitionextremal-constructionpattern-recognition easier-related-problempattern-recognitioncomplementary-counting ↑ Prerequisites: set-partitionsystematic-enumeration

📏 Medium solution 💡 3 insights

Problem

Pick a subset S of {1, 2, 3, …, 25} with one rule: whenever you take two members (the same one counted twice is OK), their sum must NOT be a member of S. How big can S be?

Pick an answer.

(A)

(B)

(C)

(D)

(E)

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

How to solve

Strategy Easier Related Problem

Tool #9 (Easier Problem): shrink to {1, …, 5} first. You can take {3, 4, 5} (3 elements) because smallest sum is 3 + 3 = 6 ＞ 5. That suggests the "top half" idea — picking large numbers makes every sum overshoot the universe. Tool #5 (Pattern): for {1, …, n} the top-half family {⌈ n/2 ⌉ + 1, …, n} gives ⌈ n/2 ⌉ elements; for n = 25 that is {13, …, 25} with 13 elements. Tool #1 (Diagram): draw a number line 1-25 and mark candidate elements; the picture shows that pairing i with 25 - i (or with the max M in S) blocks one of each pair from joining S. Tool #16 (Complement) captures that bound: the pairs (1,24), (2,23), …, (12,13) contribute at most 12 elements, plus the max element itself ≤ 13 total. Tool #3 (Eliminate) confirms 13 beats 14, 15, 16 in the answer list.

1STEP 1

Warm up on {1, …, 5}: take top half S = {3, 4, 5}. Smallest sum 3 + 3 = 6 exits the universe, so 3 elements work.

S = {3, 4, 5} ⊂ {1, …, 5}; min(x+y) = 6 ＞ 5

2STEP 2

Copy it to {1, …, 25}: take S = {13, …, 25}, which is 13 elements. Smallest sum 13 + 13 = 26 beats 25, so every pair is safe.

S = {13, 14, …, 25}; |S| = 13; min(x+y) = 26 ＞ 25

3STEP 3

For the ceiling, let M be the largest element: since i + (M − i) = M, each pair (i, M − i) gives at most one member of S.

if i + (M - i) = M ∈ S, then at most one of i, M - i ∈ S

4STEP 4

Counting the pairs plus M gives |S| no more than half of M rounded up; since M ≤ 25, |S| ≤ 13.

|S| ≤ ⌈

\frac{M}{2}

⌉ ≤ ⌈

\frac{25}{2}

⌉ = 13

5STEP 5

Step 2 reaches 13 and Step 4 caps at 13, so they meet: the maximum is exactly 13.

max |S| = 13

6STEP 6

Matching 13 to the answer choices lands on (B).

13 → (B)

Answer

Try another 13-element family to double-check: the odd numbers {1, 3, 5, …, 25} count exactly 13 elements. Any two odd numbers sum to an even number, and our set contains no even numbers — so x + y ∉ S holds automatically. The fact that two completely different families both hit 13 elements (and the upper bound also says 13) is strong evidence the answer is right. Cross-check the count in {13, …, 25}: 25 - 13 + 1 = 13, matches.

💡Key takeaway

This AMC 10 problem only needs Grade 6 reasoning about pair-counting and category membership you already know — start with the top-half family {13, …, 25} where every sum overshoots 25, then pair up (i, 25-i) to show 13 is also the most you could ever fit.

More like this