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$

Answer: C

Concepts:subsets extremal argument pairing and grouping

Difficulty rating: 2120

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 let $m$ be the largest element of any sum-free subset. For $1\le i<m/2,$ at most one member of $\{i,m-i\}$ can be chosen, because the two sum to $m.$ If $m$ is even, $m/2$ cannot be chosen either, since it can be used twice and $m/2+m/2=m.$ Thus besides $m$ there are at most $\lfloor(m-1)/2\rfloor$ chosen elements, for a total of at most $\lfloor(m-1)/2\rfloor+1\le10.$ Therefore the greatest possible size is $10.$ Thus, C is the correct answer.

2025 AMC 10A Problem 21

Answer: C

Difficulty rating: 2120

Solution:

Problem 21 in Other Years