Question

Las $27$ celdas de una cuadrícula $3 \times 9$ se llenan usando los números $1$ a $9$ de modo que cada fila contenga $9$ números distintos, y que cada uno de los tres bloques $3 \times 3$ resaltados con contorno grueso en el ejemplo de abajo contenga $9$ números distintos, como en las primeras tres filas de un Sudoku.

El número de formas distintas de llenar tal cuadrícula se puede escribir como $p^a \cdot q^b \cdot r^c \cdot s^d,$ donde $p,$ $q,$ $r,$ y $s$ son números primos distintos y $a,$ $b,$ $c,$ $d$ son enteros positivos. Halle $p \cdot a + q \cdot b + r \cdot c + s \cdot d.$

The $27$ cells of a $3 \times 9$ grid are filled in using the numbers $1$ through $9$ so that each row contains $9$ different numbers, and each of the three $3 \times 3$ blocks heavily outlined in the example below contains $9$ different numbers, as in the first three rows of a Sudoku puzzle.

The number of different ways to fill such a grid can be written as $p^a \cdot q^b \cdot r^c \cdot s^d,$ where $p,$ $q,$ $r,$ and $s$ are distinct prime numbers and $a,$ $b,$ $c,$ $d$ are positive integers. Find $p \cdot a + q \cdot b + r \cdot c + s \cdot d.$

Respuesta

Solución:

Llene el bloque izquierdo arbitrariamente: $9!$ formas. Sean $R_1, R_2, R_3$ los conjuntos de tres dígitos de sus filas. En el bloque central, la fila $i$ debe evitar $R_i$ (esos dígitos ya aparecen en la fila $i$ ), y las tres filas del bloque deben partir $\{1, \ldots, 9\}.$ Digamos que su fila superior toma $j$ dígitos de $R_2$ y $3 - j$ de $R_3.$ Equilibrar las tres filas obliga entonces a la fila central a tomar $3 - j$ dígitos de $R_1$ junto con los $j$ dígitos restantes de $R_3,$ y la fila inferior queda determinada. El número de elecciones de contenido es $\begin{gathered} \sum_{j=0}^{3} \binom{3}{j}\binom{3}{3-j}^2 \\ = 1 + 27 + 27 + 1 \\ = 56. \end{gathered}$

El contenido de las filas del bloque derecho queda entonces forzado (la fila $i$ toma lo que falte en la fila $i$ ), y cada una de las seis filas de los bloques central y derecho se puede ordenar internamente de $3!$ formas. El total es $\begin{gathered} 9! \cdot 56 \cdot 6^6 \\ = (2^7 \cdot 3^4 \cdot 5 \cdot 7)(2^3 \cdot 7)(2^6 \cdot 3^6) \\ = 2^{16} \cdot 3^{10} \cdot 5^1 \cdot 7^2. \end{gathered}$

Por lo tanto $p \cdot a + q \cdot b + r \cdot c + s \cdot d$ $= 2 \cdot 16 + 3 \cdot 10 + 5 \cdot 1$ $+ 7 \cdot 2 = 81.$

Fill the left block arbitrarily: $9!$ ways. Let $R_1, R_2, R_3$ be the sets of three digits in its rows. In the middle block, row $i$ must avoid $R_i$ (those digits already appear in row $i$ ), and the block's three rows must partition $\{1, \ldots, 9\}.$ Say its top row takes $j$ digits from $R_2$ and $3 - j$ from $R_3.$ Balancing the three rows then forces the middle row to take $3 - j$ digits from $R_1$ together with all $j$ remaining digits of $R_3,$ and the bottom row is determined. The number of content choices is $\begin{gathered} \sum_{j=0}^{3} \binom{3}{j}\binom{3}{3-j}^2 \\ = 1 + 27 + 27 + 1 \\ = 56. \end{gathered}$

The right block's row contents are then forced (row $i$ takes whatever is missing from row $i$ ), and each of the six rows of the middle and right blocks can be ordered internally in $3!$ ways. The total is $\begin{gathered} 9! \cdot 56 \cdot 6^6 \\ = (2^7 \cdot 3^4 \cdot 5 \cdot 7)(2^3 \cdot 7)(2^6 \cdot 3^6) \\ = 2^{16} \cdot 3^{10} \cdot 5^1 \cdot 7^2. \end{gathered}$

Therefore $p \cdot a + q \cdot b + r \cdot c + s \cdot d$ $= 2 \cdot 16 + 3 \cdot 10 + 5 \cdot 1$ $+ 7 \cdot 2 = 81.$

2025 AIME I Problema 10

Solución:

El Problema 10 en otros años