Art of Problem Solving
Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2025 AMC 10A Problems/Problem 21

Revision as of 23:44, 7 November 2025 by Oinava (talk | contribs) (Removed fake solutions and chat spam. Simplified the proof by contradiction to a direct proof.)

A 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 $\{2,4,5\}$ is not. What is the greatest possible number of elements in a sum-free subset of $\{1,2,3,...,20\}$?

$\textbf{(A) } 8 \qquad\textbf{(B) } 9 \qquad\textbf{(C) } 10 \qquad\textbf{(D) } 11 \qquad\textbf{(E) } 12$

Solution 1 (Those who know)

This problem is essentially the same as 2022 AMC 10B Problem 14.

https://artofproblemsolving.com/wiki/index.php?title=2022_AMC_10B_Problems/Problem_14

~metrixgo

Solution 2

Constructions work for $10$, such as $\{11,12,13,...,20\}$ or $\{1,3,5,...,19\}$.

Take the smallest number and look at the differences with the other numbers. With $n-1$ other numbers, there are at least $n-1$ other differences with the other numbers. However, since all of them are distinct and we are looking at the smallest number, then all of these differences are distinct. Additionally, all these differences are positive and less than 20, so we have that they are all in the set as well. Thus $n + n - 1 \leq 20$, so $n \leq 10.5$.

Thus we have proven that $\boxed{\text{(C) }10}$ is the max.

~Ant_Eater

Solution 3

Constructions work for $10$ as seen above.

We claim $10$ is the maximum. Let $n$ be the greatest element of our subset. Pair up the elements less than $n$ of the given set so that $k$ is with $n-k$. Note that only one element in each pair can be in the subset, and we have $\left\lfloor\frac{n-1}2\right\rfloor$ pairs (since for even $n$, $\frac{n}2$ can’t be in the subset). Therefore, the subset has at most $1+\left\lfloor\frac{n-1}2\right\rfloor$ elements. This function is nondecreasing, so we can plug in $20$ and find that the sum-free subset has at most $\boxed{\text{(C) }10}$ elements.

~Waddles2010


Video Solution

https://youtu.be/V_zh78Ae8xw?si=D8dEsX4ST3JORj6x ~ Pi Academy

Video Solution

https://youtu.be/gWSZeCKrOfU

~MK

Video Solution by OmegaLearn

https://youtu.be/GgNQ2yDGIRg

Video Solution by SpreadTheMathLove

https://www.youtube.com/watch?v=dAeyV60Hu5c

See also

2022 AMC10B problem14

2025 AMC 10A (Problems • Answer Key • Resources)
Preceded by
Problem 20 		Followed by
Problem 22
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 10 Problems and Solutions
2025 AMC 12A (Problems • Answer Key • Resources)
Preceded by
Problem 17 		Followed by
Problem 19
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions

These problems are copyrighted © by the Mathematical Association of America.

Retrieved from "https://wiki.aopstest.com/wiki/index.php?title=2025_AMC_10A_Problems/Problem_21&oldid=267417"