2025 AMC 10A Problem 21

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

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<\frac{m}{2},

at most one member of

\{i,m-i\}

can be chosen, because the two sum to

m.

m

is even,

\frac{m}{2}

cannot be chosen either, since it can be used twice and

\frac{m}{2}+\frac{m}{2}=m.

Thus besides

m

there are at most

\lfloor\frac{m-1}{2}\rfloor

chosen elements, for a total of at most

\lfloor\frac{m-1}{2}\rfloor+1\le10.

Therefore the greatest possible size is

10.

Thus, C is the correct answer.