1992 AMC 12 第 23 题

Question

若

S

是

\{1,2,3,\ldots,50\}

的子集，且

S

中任意两个不同元素之和都不能被

7

整除，则这样的子集最多能有多少个元素？

What is the size of the largest subset

S

of

\{1,2,3,\ldots,50\}

such that no pair of distinct elements of

S

has a sum divisible by

7?

6

7

14

22

23

答案：E

知识点：模运算 residue classes extremal set

难度评级：2170

小提示：

按模

7

的余数将这些整数分组

Group the integers by their residues modulo

7

大提示：

将余数类

1

与

6

、

2

与

5

、

3

与

4

分别配对，并单独处理余数类

0

Pair residue classes

1

with

6,

2

with

5,

and

3

with

4

; treat residue

0

separately

解答：

余数类

1,2,\ldots,6,0

分别含有

8,7,7,7,7,7,7

个数。在每对互补余数类

(1,6),(2,5),(3,4)

中，我们至多能从一个余数类取数，并且至多取一个

7

的倍数。因此

\begin{aligned} |S|&\le\max(8,7)+\max(7,7)\\ &\qquad+\max(7,7)+1=23 \end{aligned}\text{。}

取所有模

7

余

1

、

2

或

3

的数，再加上一个

7

的倍数，便能达到

23

个。

因此正确答案是 E。

The residue classes

1,2,\ldots,6,0

contain

8,7,7,7,7,7,7

numbers, respectively. We may take numbers from at most one class in each complementary pair

(1,6),(2,5),(3,4),

and at most one multiple of

7.

Thus

\begin{aligned} |S|&\le\max(8,7)+\max(7,7)\\ &\qquad+\max(7,7)+1=23. \end{aligned}

Taking every number whose residue modulo

7

is

1,

2,

or

3,

together with one multiple of

7,

attains

23.

Thus the correct answer is E.

1992 AMC 12 第 23 题

答案：E

难度评级：2170

小提示：

大提示：

解答：

其他年份的第 23 题