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:

The set $\{11, 12, \ldots, 20\}$ has $10$ elements and is sum-free, since any two elements sum to at least $22 \gt 20.$

For the upper bound, let $a_1 \lt a_2 \lt \cdots \lt a_k$ be a sum-free subset. Each difference $a_k - a_i$ for $i \lt k$ cannot lie in $S,$ because $(a_k - a_i) + a_i = a_k \in S$ would violate sum-freeness.

These $k - 1$ differences are distinct, lie in $\{1, \ldots, 19\},$ and are disjoint from the $k$ elements of $S.$ So $k + (k - 1) \le 20,$ giving $k \le 10.$

Thus, the correct answer is C.

2025 AMC 12A Problem 15

Solution:

Problem 15 in Other Years