2021 AMC 12A Fall 第 25 题

Question

令

m \ge 5

为奇整数，并令

D(m)

表示满足下列条件的四元组

(a_1, a_2, a_3, a_4)

的个数：四个分量是互不相同的整数，且对所有

i

都有

1 \le a_i \le m

，并且

m

整除

a_1 + a_2 + a_3 + a_4

。存在一个多项式

q(x) = c_3x^3 + c_2x^2 + c_1x + c_0

使得对所有奇整数

m \ge 5

都有

D(m) = q(m)

。

c_1

是多少？

Let

m \ge 5

be an odd integer, and let

D(m)

denote the number of quadruples

(a_1, a_2, a_3, a_4)

of distinct integers with

1 \le a_i \le m

for all

i

such that

m

divides

a_1 + a_2 + a_3 + a_4.

There is a polynomial

q(x) = c_3x^3 + c_2x^2 + c_1x + c_0

such that

D(m) = q(m)

for all odd integers

m \ge 5.

What is

c_1?

-6

-1

4

6

11

答案：E

知识点：模运算单位根多项式

难度评级：2650

小提示：

先数出所有和为

0\pmod m

的有序剩余类四元组，再对坐标相等的情形做容斥

First count all ordered residue quadruples summing to

0\pmod m,

then use inclusion-exclusion on equal coordinates

大提示：

把坐标重合的情形按一对相等、两对相等、三个相等、四个全相等来分类；

m

为奇数保证了乘以

2

和乘以

4

都可逆

Group collision patterns as one pair, two pairs, a triple, or all four equal; odd

m

makes multiplication by

2

and

4

invertible

解答：

把

1,2,\ldots,m

看作模

m

的全部剩余类。若不要求各分量互不相同，则前三个分量可以任取，第四个分量随之唯一确定，于是共有

m^3

个有序四元组。

按哪些坐标相等来划分并做容斥，即可得到其余各项。恰有一对坐标相等的选法有

6

种，每种留下

m^2

组解，共贡献

-6m^2

。

3

种“两对相等”的划分贡献

+3m

。

4

种“三个相等加一个单独”的划分的容斥系数为

2

，贡献

+8m

。最后，四个全相等的划分系数为

-6

，且只有一组解。（这里

m

为奇数保证了

2

和

4

模

m

可逆。）因此

\begin{aligned} D(m)&=m^3-6m^2 \\ &\quad {}+11m-6 \\ &=(m-1)(m-2) \\ &\quad {}\cdot(m-3) \end{aligned}\text{。}

于是

c_1=11

。

所以正确答案是 E。

Regard

1,2,\ldots,m

as all residues modulo

m.

Without the distinctness condition, the first three entries are arbitrary and the fourth is determined, giving

m^3

ordered quadruples.

Inclusion-exclusion over equal-coordinate partitions gives the remaining terms. There are

6

choices of one equal pair, each leaving

m^2

solutions, for

-6m^2.

The

3

two-pair partitions contribute

+3m.

The

4

triple-and-single partitions have inclusion-exclusion coefficient

2

and contribute

+8m.

Finally, the all-equal partition has coefficient

-6

and one solution. (Here odd

m

makes

2

and

4

invertible modulo

m.

) Therefore

\begin{aligned} D(m)&=m^3-6m^2 \\ &\quad {}+11m-6 \\ &=(m-1)(m-2) \\ &\quad {}\cdot(m-3). \end{aligned}

Hence

c_1=11.

Thus, the correct answer is E.

2021 AMC 12A Fall 第 25 题

答案：E

难度评级：2650

小提示：

大提示：

解答：

其他年份的第 25 题