Question

Sea $N$ el número de formas de colocar los enteros del $1$ al $12$ en las $12$ celdas de una cuadrícula de $2 \times 6$ de modo que, para cualesquiera dos celdas que comparten un lado, la diferencia entre los números de esas celdas no sea divisible por $3.$ Abajo se muestra una forma de hacerlo. Halla el número de divisores enteros positivos de $N.$

Let $N$ be the number of ways to place the integers $1$ through $12$ in the $12$ cells of a $2 \times 6$ grid so that for any two cells sharing a side, the difference between the numbers in those cells is not divisible by $3.$ One way to do this is shown below. Find the number of positive integer divisors of $N.$

Respuesta

Respuesta: 144

Conceptos:aritmética modular permutaciones de multiconjuntos conteo de factores

Nivel de dificultad: 2920

Solución:

La condición dice que las celdas adyacentes tienen residuos distintos módulo $3.$ Cada clase de residuos entre $1, \ldots, 12$ tiene exactamente $4$ miembros, así que $N = K \cdot (4!)^3,$ donde $K$ es el número de formas de rellenar la cuadrícula con residuos $0, 1, 2,$ cada uno usado $4$ veces, con celdas adyacentes distintas.

Una columna es un par ordenado $(a, b)$ de residuos distintos. Si la columna actual es $(a, b)$ y $e$ es el tercer residuo, la siguiente columna debe ser una de $(b, a),$ $(b, e),$ $(e, a):$ cada uno de los tres pares no ordenados $\{a,b\},$ $\{b,e\},$ $\{a,e\}$ aparece en exactamente una orientación permitida. Así que un patrón de residuos queda determinado por la sucesión de seis pares no ordenados junto con la orientación de la primera columna. Como cada residuo debe aparecer $4$ veces, cada uno de los tres pares debe usarse exactamente dos veces, lo que da $\frac{6!}{2!\,2!\,2!} = 90$ sucesiones y $K = 2 \cdot 90 = 180.$

Por lo tanto $N = 180 \cdot 24^3$ $= 2{,}488{,}320$ $= 2^{11} \cdot 3^5 \cdot 5,$ que tiene $12 \cdot 6 \cdot 2 = 144$ divisores positivos.

The condition says adjacent cells have different residues mod $3.$ Each residue class among $1, \ldots, 12$ has exactly $4$ members, so $N = K \cdot (4!)^3,$ where $K$ is the number of ways to fill the grid with residues $0, 1, 2,$ each used $4$ times, with adjacent cells different.

A column is an ordered pair $(a, b)$ of distinct residues. If the current column is $(a, b)$ and $e$ is the third residue, the next column must be one of $(b, a),$ $(b, e),$ $(e, a):$ each of the three unordered pairs $\{a,b\},$ $\{b,e\},$ $\{a,e\}$ occurs in exactly one allowed orientation. So a residue pattern is determined by the sequence of six unordered pairs together with the orientation of the first column. Since each residue must appear $4$ times, each of the three pairs must be used exactly twice, giving $\frac{6!}{2!\,2!\,2!} = 90$ sequences and $K = 2 \cdot 90 = 180.$

Therefore $N = 180 \cdot 24^3$ $= 2{,}488{,}320$ $= 2^{11} \cdot 3^5 \cdot 5,$ which has $12 \cdot 6 \cdot 2 = 144$ positive divisors.

2023 AIME II Problema 10

Respuesta: 144

Nivel de dificultad: 2920

Solución:

El Problema 10 en otros años