2024 AMC 8 第 16 题

Question

Minh 把

1

到

81

的数字以某种顺序填入一个

9 \times 9

网格。她计算每一行和每一列中数字的乘积。最少有多少行和列的乘积能被

3

整除？

Minh enters the numbers

1

through

81

into the cells of a

9 \times 9

grid in some order. She calculates the product of the numbers in each row and column. What is the least number of rows and columns that could have a product divisible by

3?

8

9

10

11

12

答案：D

知识点：整除性最优化极端原理

难度评级：1660

小提示：

只有

3

的倍数会使所在行或列的乘积能被

3

整除

Only multiples of

3

make a row or column product divisible by

3

大提示：

用尽可能少的行和列覆盖

27

个

3

的倍数

Cover the

27

multiples of

3

using as few rows and columns as possible

视频讲解：

Click to load, then click again to play

文字解答：

从

1

到

81

27

个

3

的倍数。一行或一列的乘积能被

3

整除，当且仅当它至少含有一个这样的倍数。

设有

r

行和

c

列的乘积能被

3

整除。每个

3

的倍数都必须位于这

r

行之一，同时也位于这

c

列之一，否则它会再制造出一行或一列被标记。因此

27

个倍数必须装入

rc

个交叉格中。若

r+c\le10

，则

rc\le25

，格子不够。因此至少要标记

11

行和列。

可以把

25

个

3

的倍数放入一个

5\times5

区块，再把剩下的

2

个放在第六列中，且位于其中两行内。这样恰好标记

5

行和

6

列，共

11

。

正确答案是 D。

There are

27

multiples of

3

from

1

through

81

. A row or column has product divisible by

3

exactly when it contains at least one of these multiples.

Suppose

r

rows and

c

columns have products divisible by

3

. Every multiple of

3

must lie in one of those

r

rows and also in one of those

c

columns, or else it would create another marked row or column. Thus the

27

multiples must fit in the

rc

intersection cells. If

r+c\le10

, then

rc\le25

, which is too small. So at least

11

rows and columns are needed.

This can be done by placing

25

multiples of

3

in a

5\times5

block, then placing the remaining

2

multiples in a sixth column within two of those same rows. Then exactly

5

rows and

6

columns are marked, for a total of

11

.

Thus, D is the correct answer.

2024 AMC 8 第 16 题

答案：D

难度评级：1660

小提示：

大提示：

视频讲解：

文字解答：

其他年份的第 16 题