2022 AMC 10B Problem 14

This asks for the most numbers possible, so there are two halves: find a set that works, then show nothing bigger can work.

Part 1: thirteen numbers is possible.

1. Take the top half, $13, 14, \ldots, 25$. That is $13$ numbers.
2. The smallest sum you can make is $13 + 13 = 26$, which is bigger than $25$. So no sum lands back in the set.

Part 2: fourteen numbers is impossible.

3. The largest number in the set limits what else can go in, so look at it first. Suppose the largest number is $25$.
4. Pair up the numbers below $25$ so that each pair adds to $25$:
$$1{+}24,\ 2{+}23,\ 3{+}22,\ \ldots,\ 12{+}13.$$
That is $12$ pairs, and every number from $1$ to $24$ is in exactly one pair.
5. The set cannot hold both numbers of a pair. For example, if it had $5$ and $20$, then $5 + 20 = 25$ would be in the set, which breaks the rule.
6. So below $25$ the set has at most one number from each of the $12$ pairs. Adding $25$ itself gives at most $12 + 1 = 13$ numbers.
7. If the largest number is even, say $24$, pair up $1{+}23, 2{+}22, \ldots, 11{+}13$: that is $11$ pairs, and $12$ is left over. The set cannot contain $12$, because $12 + 12 = 24$. So there are at most $11 + 1 = 12$ numbers.
8. If the largest number is smaller than $24$, there are even fewer numbers below it, and the same pairing gives an even smaller limit.

Thirteen is possible and fourteen is not.

The answer is $\boxed{\textbf{(B)}\ 13}$.

For "how many numbers can you pick without breaking a rule" questions, look at one special number (here the largest) and see what it forbids. Pairing the other numbers so each pair "competes" for one place turns the question into counting pairs. The words "not necessarily distinct" matter: they are why half of an even largest number is not allowed.

The odd numbers $1, 3, 5, \ldots, 25$ also make a set of $13$ that works, because odd plus odd is always even. Finding two different sets of $13$ and no set of $14$ is a good sign, but only the pairing argument proves that $14$ is impossible.

Construction. Take $S = \{13, 14, \dots, 25\}$, which has $13$ elements. The smallest possible sum of two elements is $13 + 13 = 26 > 25$, so no sum lands in $S$.

Upper bound. Let $M$ be the largest element of $S$. Every other element lies in $\{1, \dots, M-1\}$. Group these numbers into pairs $\{k, M-k\}$ with $k < M - k$. If both members of a pair were in $S$, their sum $M$ would be in $S$, forbidden. Also, if $M$ is even, the number $M/2$ cannot be in $S$, since $M/2 + M/2 = M$.

• If $M$ is odd, $\{1, \dots, M-1\}$ splits into $\frac{M-1}{2}$ pairs, each contributing at most one element, so $|S| \le \frac{M-1}{2} + 1 = \frac{M+1}{2} \le \frac{26}{2} = 13$.
• If $M$ is even, there are $\frac{M-2}{2}$ pairs plus the excluded $M/2$, so $|S| \le \frac{M-2}{2} + 1 = \frac{M}{2} \le 12$.

Either way $|S| \le 13$, and $13$ is achieved.

The answer is $\boxed{\textbf{(B)}\ 13}$.