Question

设 $S$ 是 $\{1, 2, 3, \ldots, 30\}$ 的一个子集，且 $S$ 中任意两个不同元素的和都不能被 $5$ 整除。 $S$ 的最大可能大小是多少？

Let $S$ be a subset of $\{1, 2, 3, \ldots, 30\}$ with the property that no pair of distinct elements in $S$ has a sum divisible by $5.$ What is the largest possible size of $S?$

$10$

$13$

$15$

$16$

$18$

答案：B

知识点：模运算子集极端原理

难度评级：1800

解答：

按模 $5$ 的余数将 $\{1, \ldots, 30\}$ 分组；每类有 $6$ 个数。当余数组合为 $0{+}0$ 、 $1{+}4$ 或 $2{+}3$ 时，和能被 $5$ 整除。

因此 $S$ 最多使用一个 $\equiv 0$ 的数，并且在 $\{1\}, \{4\}$ 两类中最多选一类，在 $\{2\}, \{3\}$ 两类中最多选一类。这最多允许 $1 + 6 + 6 = 13$ 个数。

集合 $\{1, 2, 6, 7, 11, 12$ $16, 17, 21, 22$ $26, 27, 30\}$ 可以达到 $13$ ，所以最大值为 $13$ 。

因此，正确答案是 B。

Group $\{1, \ldots, 30\}$ by residue modulo $5;$ each class has $6$ numbers. A sum is divisible by $5$ when the residues are $0{+}0,$ $1{+}4,$ or $2{+}3.$

So $S$ can use at most one number $\equiv 0,$ and only one of the classes $\{1\}, \{4\}$ and only one of $\{2\}, \{3\}.$ That allows at most $1 + 6 + 6 = 13$ numbers.

The set $\{1, 2, 6, 7, 11, 12,$ $16, 17, 21, 22,$ $26, 27, 30\}$ achieves $13,$ so the maximum is $13.$

Thus, the correct answer is B.

2012 AMC 12A 第 17 题

答案：B

难度评级：1800

解答：

其他年份的第 17 题