AMC 10 · 2025 · #21
Grade 3 number-theoryA set of numbers is called sum-free if whenever x and y are (not necessarily distinct) elements of the set, x+y is not an element of the set. For example, {1,4,6} and the empty set are sum-free, but {1,4,5} is not. What is the greatest possible number of elements in a sum-free subset of {1,2,3,...,20}?
Pick an answer.
AMC 10 2025 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.
Try it yourself first — the explanation is most useful after you’ve attempted it.
Toolkit + CCSS Solution
Understand
Restated: 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.
Givens: The universe is $\{1,2,3,\dots,20\}$; A set is sum-free if for all elements $x,y$ (possibly $x=y$), the sum $x+y$ is not in the set; $\{1,4,6\}$ is sum-free; $\{1,4,5\}$ is not because $1+4=5$; Answer choices: (A) $8$, (B) $9$, (C) $10$, (D) $11$, (E) $12$
Unknowns: The greatest possible size of a sum-free subset of $\{1,2,\dots,20\}$
Understand
Restated: 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.
Givens: The universe is $\{1,2,3,\dots,20\}$; A set is sum-free if for all elements $x,y$ (possibly $x=y$), the sum $x+y$ is not in the set; $\{1,4,6\}$ is sum-free; $\{1,4,5\}$ is not because $1+4=5$; Answer choices: (A) $8$, (B) $9$, (C) $10$, (D) $11$, (E) $12$
Plan
Primary tool: #14 Extreme Principle
Secondary: #7 Identify Subproblems, #6 Guess and Check, #16 Change Focus / Count the Complement, #2 Make a Systematic List, #3 Eliminate Possibilities
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$.
Execute — Answer: C
2.NBT.B.5 Step 1 Build a sum-free set of size 10
- First just find a set that works.
- Guess the top ten numbers $A=\{11,12,13,\dots,20\}$.
- The smallest sum of two of them is $11+11=22$, and every other sum is even bigger.
- Since $22>20$, no sum of two members can land back in the range at all, let alone inside $A$.
- So $A$ is sum-free and has $10$ elements.
- (The all-odds set $\{1,3,5,\dots,19\}$ also works, since odd $+$ odd is even and there are no evens to hit.) This shows $10$ is reachable.
💡 Pick numbers so large that any two of them already overshoot $20$, so no sum can come back.
2.OA.C.3 Step 2 Focus on the largest element
- Now prove you can never beat $10$.
- Take any sum-free subset $A$ and let $m$ be its largest element.
- This is the Extreme Principle: instead of juggling the whole set, pin down one boundary value and let it constrain everything else.
- Only $m$ can be $\ge m$; every other element of $A$ lives strictly below $m$, in $\{1,2,\dots,m-1\}$.
💡 The biggest element sets the ceiling, so all the action happens beneath it.
2.OA.B.2 Step 3 Pair numbers by what adds to m
- Group the numbers below $m$ into complementary pairs that add to $m$: $\{1,m-1\},\{2,m-2\},\{3,m-3\},\dots$.
- Here is the key: because $m$ is in $A$, a pair can never be fully inside $A$.
- If both $x$ and $m-x$ were in $A$, their sum $x+(m-x)=m$ would be a member of $A$, which is forbidden.
- So each pair hands over at most one element to $A$.
💡 Two numbers that add up to a banned total can't both be invited.
3.OA.D.9 Step 4 Count the cap when m is odd
- Say $m$ is odd, $m=2k-1$.
- Then the numbers $1,\dots,m-1$ split perfectly into $k-1$ complementary pairs with nothing left over.
- Listing them: $\{1,m-1\},\{2,m-2\},\dots,\{k-1,k\}$.
- Each pair gives at most one element, and $m$ itself gives one more, so $|A|\le (k-1)+1=k=\tfrac{m+1}{2}$.
- The largest odd $m\le 20$ is $19$, giving $\tfrac{19+1}{2}=10$.
💡 An odd top value pairs off everything below it cleanly, so half of them (plus the top) is the ceiling.
2.OA.C.3 Step 5 Count the cap when m is even
- Say $m$ is even, $m=2k$.
- The pairs are $\{1,m-1\},\dots,\{k-1,k+1\}$, and the middle number $k$ is left alone.
- But $k$ is also banned: $k+k=2k=m$ is in $A$, so $k$ cannot join.
- That leaves $k-1$ pairs (at most one each) plus $m$ itself, so $|A|\le (k-1)+1=k=\tfrac{m}{2}\le\tfrac{20}{2}=10$.
- Even here the cap is $10$.
💡 An even top value also blocks its own half, so the ceiling is still exactly half of $m$.
3.OA.D.9 Step 6 Combine and rule out 11 and 12
- Both cases give $|A|\le 10$ for any sum-free subset, so $11$ and $12$ are impossible, ruling out (D) and (E).
- Step 1 built an actual set of size $10$, so the bound is achieved.
- The greatest possible number of elements is exactly $10$, which is choice (C).
💡 A proven ceiling of $10$ plus a real example of $10$ pins the answer exactly.
2.NBT.B.5 First just find a set that works. Guess the top ten numbers $A={11,12,13,\dots, 2.OA.C.3 Now prove you can never beat $10$. Take any sum-free subset $A$ and let $m$ be i 2.OA.B.2 Group the numbers below $m$ into complementary pairs that add to $m$: ${1,m-1} 3.OA.D.9 Say $m$ is odd, $m=2k-1$. Then the numbers $1,\dots,m-1$ split perfectly into $k 2.OA.C.3 Say $m$ is even, $m=2k$. The pairs are $\{1,m-1\},\dots,\{k-1,k+1\}$, and the mi 3.OA.D.9 Both cases give $|A|\le 10$ for any sum-free subset, so $11$ and $12$ are imposs Review
Reasonableness: The bound $|A|\le m/2\le 10$ is tight from both directions: the odd top $m=19$ gives the all-odds set $\{1,3,\dots,19\}$ of size $10$, and the even top $m=20$ gives $\{11,\dots,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,\dots\}$ 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$.
Alternative: Instead of pairing, split $\{1,\dots,20\}$ into the two halves $L=\{1,\dots,10\}$ and $H=\{11,\dots,20\}$ and think about how many elements a sum-free set can hold. $H$ alone is already sum-free with $10$ elements, so the answer is at least $10$; the complementary-pair bound of Step 3 (applied to the set's largest element) shows you can never exceed $10$. This 'top-half construction plus extreme-element bound' is the standard route to the classic result that the biggest sum-free subset of $\{1,\dots,n\}$ has $\lceil n/2\rceil$ elements, here $\lceil 20/2\rceil=10$.
CCSS standards used (min grade 3)
2.NBT.B.5Fluently add and subtract within 100 (Checking the construction: the smallest sum $11+11=22$ exceeds $20$, so $\{11,\dots,20\}$ is sum-free.)2.OA.C.3Determine whether a group of objects has an odd or even number (Splitting the argument by the parity of the largest element $m$, and seeing that an even $m$ blocks its own half $k$ via $k+k=m$.)2.OA.B.2Fluently add and subtract within 20 using mental strategies (Forming the complementary pairs $\{x, m-x\}$ that add up to $m$ (with $m\le 20$).)3.OA.D.9Identify arithmetic patterns and explain using properties of operations (Recognizing the 'at most one per pair' pattern, turning it into the count $m/2$, and concluding the cap of $10$ rules out $11$ and $12$.)
⭐ 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.
⭐ 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.
More like this
Same archetype — closest grade level first.
