AMC12 2012 A

AMC12 2012 A · Q17

AMC12 2012 A · Q17. It mainly tests Casework, Remainders & modular arithmetic.

Let $S$ be a subset of $\{1,2,3,\dots,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$?

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

(A) 10 10

(B) 13 13

(D) 16 16

(E) 18 18

Answer

Correct choice: (B)

正确答案：（B）

Solution

Of the integers from $1$ to $30$, there are six each of $0,1,2,3,4\ (\text{mod}\ 5)$. We can create several rules to follow for the elements in subset $S$. No element can be $1\ (\text{mod}\ 5)$ if there is an element that is $4\ (\text{mod}\ 5)$. No element can be $2\ (\text{mod}\ 5)$ if there is an element that is $3\ (\text{mod}\ 5)$. Thus we can pick 6 elements from either $1\ (\text{mod}\ 5)$ or $4\ (\text{mod}\ 5)$ and 6 elements from either $2\ (\text{mod}\ 5)$ or $3\ (\text{mod}\ 5)$ for a total of $6+6=12$ elements. Considering $0\ (\text{mod}\ 5)$, there can be one element that is so because it will only be divisible by $5$ if paired with another element that is $0\ (\text{mod}\ 5)$. The final answer is $\boxed{\textbf{(B)}\ 13}$.

在从 $1$ 到 $30$ 的整数中，模 $5$ 余 $0,1,2,3,4\ (\text{mod}\ 5)$ 的各有 $6$ 个。我们可以为子集 $S$ 的元素制定若干规则：如果存在一个元素是 $4\ (\text{mod}\ 5)$，则不能有元素是 $1\ (\text{mod}\ 5)$；如果存在一个元素是 $3\ (\text{mod}\ 5)$，则不能有元素是 $2\ (\text{mod}\ 5)$。因此，我们可以从 $1\ (\text{mod}\ 5)$ 或 $4\ (\text{mod}\ 5)$ 中任选一类取 $6$ 个元素，并从 $2\ (\text{mod}\ 5)$ 或 $3\ (\text{mod}\ 5)$ 中任选一类取 $6$ 个元素，总共 $6+6=12$ 个。再考虑 $0\ (\text{mod}\ 5)$ 的情况，最多只能取其中 $1$ 个元素，因为只有与另一个 $0\ (\text{mod}\ 5)$ 的元素配对时和才会被 $5$ 整除。最终答案是 $\boxed{\textbf{(B)}\ 13}$。

Topics