2012 AMC 12A 第 17 题

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

的余数给这些数分类；每一类都有

6

个数

Sort the numbers by their remainder modulo

5

; there are

6

numbers in each class

大提示：

余数

1

和

4

不能同时出现，

2

和

3

也不能同时出现，并且最多只能选一个

5

的倍数

Residues

1

and

4

cannot both appear, nor can

2

and

3,

and at most one multiple of

5

is allowed

解答：

按模

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 题