Question

Hay $N$ permutaciones $(a_1, a_2, \ldots, a_{30})$ de $1, 2, \ldots, 30$ tales que para $m \in \{2, 3, 5\},$ $m$ divide a $a_{n+m} - a_n$ para todos los enteros $n$ con $1 \le n \lt n + m \le 30.$ Halla el residuo cuando $N$ se divide entre $1000.$

There are $N$ permutations $(a_1, a_2, \ldots, a_{30})$ of $1, 2, \ldots, 30$ such that for $m \in \{2, 3, 5\},$ $m$ divides $a_{n+m} - a_n$ for all integers $n$ with $1 \le n \lt n + m \le 30.$ Find the remainder when $N$ is divided by $1000.$

Respuesta

Solución:

Para cada $m \in \{2, 3, 5\},$ la condición $a_{n+m} \equiv a_n \pmod{m}$ significa que el residuo de $a_n$ módulo $m$ depende solo de $n \bmod m,$ definiendo una aplicación $\sigma_m$ de residuos a residuos. Cada clase de residuos de posiciones tiene $\frac{30}{m}$ miembros, y lo mismo cada clase de residuos de valores; si $\sigma_m$ enviara dos clases de posiciones a la misma clase de valores, los $\frac{30}{m}$ valores de esa clase tendrían que llenar $\frac{60}{m}$ posiciones, lo cual es imposible. Así que cada $\sigma_m$ es una permutación de los residuos módulo $m.$

Recíprocamente, por el teorema chino del resto cada posición $n \in \{1, \ldots, 30\}$ corresponde a una única tripleta $(n \bmod 2,\, n \bmod 3,\, n \bmod 5),$ y lo mismo para los valores. Cualquier elección de permutaciones $(\sigma_2, \sigma_3, \sigma_5)$ determina, por lo tanto, una única permutación válida de $1, \ldots, 30,$ que envía la tripleta de posición a la tripleta de valor prescrita.

Por lo tanto $N = 2! \cdot 3! \cdot 5! = 1440,$ y el residuo al dividir entre $1000$ es $440.$

For each $m \in \{2, 3, 5\},$ the condition $a_{n+m} \equiv a_n \pmod{m}$ means the residue of $a_n$ modulo $m$ depends only on $n \bmod m,$ defining a map $\sigma_m$ from residues to residues. Each residue class of positions has $\frac{30}{m}$ members, and so does each residue class of values; if $\sigma_m$ sent two position classes to the same value class, that class's $\frac{30}{m}$ values would have to fill $\frac{60}{m}$ positions, which is impossible. So each $\sigma_m$ is a permutation of the residues modulo $m.$

Conversely, by the Chinese remainder theorem each position $n \in \{1, \ldots, 30\}$ corresponds to a unique triple $(n \bmod 2,\, n \bmod 3,\, n \bmod 5),$ and likewise for values. Any choice of permutations $(\sigma_2, \sigma_3, \sigma_5)$ therefore determines a unique valid permutation of $1, \ldots, 30,$ sending the position triple to the prescribed value triple.

Hence $N = 2! \cdot 3! \cdot 5! = 1440,$ and the remainder upon division by $1000$ is $440.$

2011 AIME II Problema 14

Solución:

El Problema 14 en otros años