AMC10 2022 B

AMC10 2022 B · Q14

AMC10 2022 B · Q14. It mainly tests Casework, Invariants.

Suppose that $S$ is a subset of $\left\{ 1, 2, 3, \ldots , 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?

设$S$是$\left\{ 1, 2, 3, \ldots , 25 \right\}$的子集，使得$S$中任意两个（不一定不同）元素的和都不在$S$中。$S$最多能包含多少个元素？

(A) 12 12

(B) 13 13

(D) 15 15

(E) 16 16

Answer

Correct choice: (B)

正确答案：（B）

Solution

Let $M$ be the largest number in $S$. We categorize numbers $\left\{ 1, 2, \ldots , M-1 \right\}$ (except $\frac{M}{2}$ if $M$ is even) into $\left\lfloor \frac{M-1}{2} \right\rfloor$ groups, such that the $i$th group contains two numbers $i$ and $M-i$. Recall that $M \in S$ and the sum of two numbers in $S$ cannot be equal to $M$, and the sum of numbers in each group above is equal to $S$. Thus, each of the above $\left\lfloor \frac{M-1}{2} \right\rfloor$ groups can have at most one number in $S$. Therefore, \begin{align*} |S| & \leq 1 + \left\lfloor \frac{M-1}{2} \right\rfloor \\ & \leq 1 + \left\lfloor \frac{25}{2} \right\rfloor \\ & = 13. \end{align*} Next, we construct an instance of $S$ with $|S| = 13$. Let $S = \left\{ 13, 14, \ldots , 25 \right\}$. Thus, this set is feasible. Therefore, the most number of elements in $S$ is $\boxed{\textbf{(B) }13}$.

设$M$为$S$中的最大数。我们将$\left\{ 1, 2, \ldots , M-1 \right\}$（若$M$为偶数则除去$\frac{M}{2}$）分成$\left\lfloor \frac{M-1}{2} \right\rfloor$组，第$i$组包含$i$和$M-i$。回想$M \in S$，$S$中两数和不能等于$M$，且上述每组两数和等于$M$。因此，上述$\left\lfloor \frac{M-1}{2} \right\rfloor$组中$S$最多取一个数。因此， \begin{align*} |S| & \leq 1 + \left\lfloor \frac{M-1}{2} \right\rfloor \\ & \leq 1 + \left\lfloor \frac{25}{2} \right\rfloor \\ & = 13. \end{align*} 接下来构造$|S| = 13$的例子：$S = \left\{ 13, 14, \ldots , 25 \right\}$。此集满足条件。因此$S$最多元素个数为$\boxed{\textbf{(B) }13}$。

Topics