Question

Los enteros de $1$ a $64$ se colocan en algún orden en una cuadrícula de $8 \times 8$ celdas con un número en cada celda. Sea $a_{i,j}$ el número colocado en la celda de la fila $i$ y la columna $j,$ y sea $M$ la suma de las diferencias absolutas entre celdas adyacentes. Es decir, $\scriptsize M = \sum_{i=1}^{8} \sum_{j=1}^{7} \left( |a_{i,j+1} - a_{i,j}| + |a_{j+1,i} - a_{j,i}| \right).$ Halle el resto cuando el máximo valor posible de $M$ se divide por $1000.$

The integers from $1$ to $64$ are placed in some order into an $8 \times 8$ grid of cells with one number in each cell. Let $a_{i,j}$ be the number placed in the cell in row $i$ and column $j,$ and let $M$ be the sum of the absolute differences between adjacent cells. That is, $\scriptsize M = \sum_{i=1}^{8} \sum_{j=1}^{7} \left( |a_{i,j+1} - a_{i,j}| + |a_{j+1,i} - a_{j,i}| \right).$ Find the remainder when the maximum possible value of $M$ is divided by $1000.$

Respuesta

Solución:

Considere la cuadrícula como un grafo cuyas $112$ aristas unen celdas adyacentes. Cada arista aporta el valor de su extremo mayor positivamente y el del menor negativamente, así que $M = \sum_v c_v a_v,$ donde $a_v$ es la entrada en la celda $v$ y $c_v$ es el número de vecinos de $v$ con entradas menores menos el número con entradas mayores. Entonces $|c_v| \le \deg(v),$ que es $4$ para las $36$ celdas interiores, $3$ para las $24$ celdas de borde, y $2$ para las $4$ esquinas, y $\sum_v c_v = 0$ ya que cada arista aporta $+1$ y $-1.$

Como $\sum_v c_v = 0,$ $\begin{aligned} M &= \sum_v c_v \left(a_v - \tfrac{65}{2}\right) \\ &\le \sum_v \deg(v)\left|a_v - \tfrac{65}{2}\right|. \end{aligned}$ Por la desigualdad del reordenamiento esto se maximiza emparejando los $36$ valores más lejanos de $\frac{65}{2}$ (a saber $1$ – $18$ y $47$ – $64,$ cuyas desviaciones suman $828$ ) con las celdas interiores, los siguientes $24$ valores ( $19$ – $30$ y $35$ – $46,$ que suman $192$ ) con las celdas de borde, y $31$ – $34$ (que suman $4$ ) con las esquinas. Por lo tanto $M \le 4 \cdot 828 + 3 \cdot 192 + 2 \cdot 4$ $= 3896.$

La igualdad requiere que cada celda que contiene un valor a lo sumo $32$ sea menor que todos sus vecinos y que todo valor al menos $33$ sea mayor, lo que un tablero de ajedrez logra: ponga $1$ – $32$ en las celdas negras ( $1$ – $18$ en las negras interiores, $19$ – $30$ en las negras de borde, $31$ – $32$ en las esquinas negras) y $33$ – $64$ en las celdas blancas ( $33$ – $34$ en las esquinas, $35$ – $46$ en los bordes, $47$ – $64$ en el interior). Cada par de vecinos entonces compara blanco sobre negro, así que $M = 3896,$ y la respuesta es $3896 \bmod 1000 = 896.$

View the grid as a graph whose $112$ edges join adjacent cells. Each edge contributes its larger endpoint value positively and its smaller one negatively, so $M = \sum_v c_v a_v,$ where $a_v$ is the entry in cell $v$ and $c_v$ is the number of neighbors of $v$ with smaller entries minus the number with larger entries. Then $|c_v| \le \deg(v),$ which is $4$ for the $36$ interior cells, $3$ for the $24$ edge cells, and $2$ for the $4$ corners, and $\sum_v c_v = 0$ since each edge contributes $+1$ and $-1.$

Because $\sum_v c_v = 0,$ $\begin{aligned} M &= \sum_v c_v \left(a_v - \tfrac{65}{2}\right) \\ &\le \sum_v \deg(v)\left|a_v - \tfrac{65}{2}\right|. \end{aligned}$ By the rearrangement inequality this is maximized by pairing the $36$ values farthest from $\frac{65}{2}$ (namely $1$ – $18$ and $47$ – $64,$ whose deviations total $828$ ) with the interior cells, the next $24$ values ( $19$ – $30$ and $35$ – $46,$ totaling $192$ ) with the edge cells, and $31$ – $34$ (totaling $4$ ) with the corners. Hence $M \le 4 \cdot 828 + 3 \cdot 192 + 2 \cdot 4$ $= 3896.$

Equality requires every cell holding a value at most $32$ to be smaller than all its neighbors and every value at least $33$ to be larger, which a checkerboard achieves: put $1$ – $32$ on the black cells ( $1$ – $18$ on interior blacks, $19$ – $30$ on edge blacks, $31$ – $32$ on black corners) and $33$ – $64$ on the white cells ( $33$ – $34$ on corners, $35$ – $46$ on edges, $47$ – $64$ in the interior). Every neighbor pair then compares white over black, so $M = 3896,$ and the answer is $3896 \bmod 1000 = 896.$

2026 AIME I Problema 11

Solución:

El Problema 11 en otros años