2022 AMC 10B Problem 14

Suppose that

S

is a subset of

\left\{ 1, 2, 3, \cdots , 25 \right\}

such that the sum of any two (not necessarily distinct) elements of

S

is never an element of

S.

What is the maximum number of elements

S

may contain?

Show solution

Solution

The set

S = \{13,14 \cdots ,25\}

has

13

elements, and every pair has sum greater than

25,

so this size is attainable. Conversely, let

m

be the maximum element of

S.

For every element of

S

satisfying

i<m,

the number

i

and the number

m-i

cannot both belong to

S.

Thus, among the numbers below

m,

at most one number can be chosen from each pair with sum

m

; if

m

is even, the middle number cannot be chosen either. Hence at most

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

elements lie below

m,

and including

m

gives at most

\lfloor \dfrac{m-1}2 \rfloor +1

elements. The maximum value of this has

m=25,

yielding

13.

Thus, the answer is B .

Tagged: subsets · extremal argument · pairing and grouping