2021 AMC 12A Fall Problema 25

Question

Sea

m \ge 5

un entero impar, y sea

D(m)

el número de cuádruplas

(a_1, a_2, a_3, a_4)

de enteros distintos con

1 \le a_i \le m

para todo

i

tal que

m

divide a

a_1 + a_2 + a_3 + a_4.

Existe un polinomio

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

tal que

D(m) = q(m)

para todos los enteros impares

m \ge 5.

¿Cuánto vale

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

Respuesta: E

Conceptos:aritmética modular raíces de la unidad polinomio

Nivel de dificultad: 2650

Pista pequeña:

Primero cuenta todas las cuádruplas ordenadas de residuos cuya suma sea

0\pmod m,

y luego usa inclusión-exclusión sobre las coordenadas iguales

First count all ordered residue quadruples summing to

0\pmod m,

then use inclusion-exclusion on equal coordinates

Pista grande:

Agrupa los patrones de coincidencia en un par, dos pares, una terna o los cuatro iguales; si

m

es impar, multiplicar por

2

o por

4

es invertible

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

m

makes multiplication by

2

and

4

invertible

Solución:

Consideremos

1,2,\ldots,m

como el conjunto completo de residuos módulo

m.

Sin la condición de que sean distintos, las tres primeras entradas son arbitrarias y la cuarta queda determinada, lo que da

m^3

cuádruplas ordenadas.

La inclusión-exclusión sobre las particiones con coordenadas iguales da los términos restantes. Hay

6

maneras de elegir un par igual, y cada una deja

m^2

soluciones, lo que aporta

-6m^2.

Las

3

particiones en dos pares aportan

+3m.

Las

4

particiones en una terna y un elemento suelto tienen coeficiente de inclusión-exclusión

2

y aportan

+8m.

Por último, la partición con los cuatro iguales tiene coeficiente

-6

y una sola solución. (Aquí, al ser

m

impar,

2

y

4

son invertibles módulo

m.

) Por lo tanto

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

Así,

c_1=11.

Por lo tanto, la respuesta correcta es 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.