Question

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?

$\ 12$

$\ 13$

$\ 14$

$\ 15$

$\ 16$

Solution:

First, note that we can make a set with size $13$ using $S = \{13,14 \cdots ,25\}.$

Now, we prove no arbitrary set of size greater than $13$ work. Let $m$ be the maximum element of $S.$ Then, for all $i$ in $S,$ we know $m-i$ isn't in $S.$

This would eliminate $\lceil{\dfrac{m-1}{2}} \rceil$ of the numbers below $m.$ This means the maximum number of elements below $m$ is $\lfloor \dfrac {m-1}2 \rfloor ,$ making the maximum number of elements $\lfloor \dfrac{m-1}2 \rfloor +1.$

The maximum value of this has $m=25,$ yielding $13.$

Thus, the answer is B .

2022 AMC 10B Problem 14

Solution:

Problem 14 in Other Years