AMC 8 2024 Problem 16
AMC8 2024 年第 16 题
鸽巢原理与策略★★★☆☆
Minh enters the numbers 1 through 81 into the cells of a 9 × 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?
Minh按照某种顺序将数字1到81填入一个9×9的网格中，并计算出每行每列的数字之积。请问至少有多少行和列的乘积可以被3整除？
- A.8
- B.9
- C.10
- D.11
- E.12
正确答案 · Correct Answer
D
解析 · Solution
解法1
注意，你可以交换/旋转任何行配置，使得所有乘积为3的行和列都位于左上角。因此这些点被限制在一个的矩形内。这个矩形的面积为$ab$，有a+b行和列可被整除。我们希望且a+b最小。如果ab=27，我们在a+b=9+3=12时达到最小值。如果ab=28，我们最佳的是a+b=7+4=11。注意如果a+b=10，则ab=25。因为25<27，没有更小的答案，所以我们得到11。
要使一行或一列的乘积可被整除，该行或列中必须有一个3的倍数。为了创建最少数量的包含3的倍数的行和列，我们必须找到一种方法将它们全部放在一起，以最小化包含3的倍数的行和列的总数。从1到81，有27个3的倍数（）。所以我们必须用3的倍数填充27个单元格。如果我们把其中25个数字放在一个5 * 5的网格中，那么就会有5行和5列（总共10个）的乘积可被整除。然而，我们有27个数字，所以还有2个数字需要放在9 * 9网格中。如果我们把这两个数字都放在第6列，但一个放在第一行，一个放在第二行（紧邻已填充的5网格），那么我们现在总共有6列，仍然有5行的乘积是3的倍数。由于6 + 5 = 11，答案是 11 。DehnTwistNil
在数字1到81中，有27个3的倍数。为了最小化行数和列数，最好的方法是构造一个正方形。然而，最接近的正方形是25，这意味着还剩下两个3的倍数。不过，你可以将这些倍数直接放在5×5正方形的上方，因此答案是。只要做得更好——Chowdhury（微小配置错误）
Solution 1
Note you can swap/rotate any configuration of rows, such that all the rows and columns that have a product of 3 are in the top left. Hence the points are bounded rectangle. This has $ab$ area and a+b rows and columns divisible. We want and a+b minimized. If ab=27, we achieve minimum with a+b=9+3=12. If ab=28,our best is a+b=7+4=11. Note if a+b=10, ab=25. Because 25<27, there is no smaller answer, and we get 11.
For a row or column to have a product divisible, there must be a multiple of 3 in the row or column. To create the least amount of rows and columns with multiples of 3, we must find a way to keep them all together, to minimize the total number of rows and columns with multiples of threes in it. From 1 to 81, there are 27 multiples of 3 (). So we have to fill 27 cells with numbers that are multiples of 3. If we put 25 of these numbers in a 5 * 5 grid, there would be 5 rows and 5 columns ( 10 in total), with products divisible. However, we have 27 numbers, so 2 numbers still need to be put in the 9 * 9 grid. If we put both numbers in the 6 th column, but one in the first row, and one in the second row, (next to the 5 grid already filled), we would have a total of 6 columns now, and still 5 rows with products that are multiples of 3. Since 6 + 5 = 11, the answer is 11. DehnTwistNil
In the numbers 1 to 81, there are 27 multiples of three. In order to minimize the rows and columns, the best way is to make a square. However, the closest square is 25, meaning there are two multiples of three remaining. However, you can place these multiples right above the 5x5 square, meaning the answer is Just be better Chowdhury (minor configuration error)
继续练习