2025 AMC 12A Problem 15

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\}?

Show solution

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.

k + (k - 1) \le 20,

giving

k \le 10.

Thus, the correct answer is C.

Tagged: subsets · extremal argument