Question

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$

Answer: E

Concepts:modular arithmetic roots of unity polynomial

Difficulty rating: 2650

Solution:

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 Problem 25

Answer: E

Difficulty rating: 2650

Solution:

Problem 25 in Other Years