Question

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, \ldots, 20\}?$

$8$

$9$

$10$

$11$

$12$

Solution:

We can reach $10.$ The odds $\{1, 3, 5, \ldots, 19\}$ are sum-free, since two odds sum to an even. So is $\{11, 12, \ldots, 20\},$ since any two of those sum past $20.$ Each has $10$ elements. Now we show you can't beat $10.$ Let $m$ be the largest element of a sum-free subset. Pair up $1, 2, \ldots, m-1$ as $\{i, m-i\}.$ A pair can't contribute both elements, or their sum $m$ would be in the set. There are $\lfloor (m-1)/2 \rfloor$ such pairs, so the subset has at most $\lfloor (m-1)/2 \rfloor + 1 \le \lfloor 19/2 \rfloor + 1 = 10$ elements. Thus, C is the correct answer.

2025 AMC 10A Problem 21

Solution:

Problem 21 in Other Years