Llenar un $n\times n$ tablero

Question

Este problema me viene molestando desde hace tiempo.

Considere un $n\times n$ tablero de ajedrez, con $n$ siendo un número entero positivo impar. En la casilla central del tablero, un $0$ se coloca. A partir de ese tablero, ¿cuántas formas hay de llenar el tablero con enteros no negativos (mayores o iguales a $0$ ) tal que no hay dos cuadrados que compartan una arista que estén llenos de números cuya diferencia sea mayor que $1$ .

El problema es fácil de hacer para $n=3$ por un simple trabajo de caja, y he encontrado que la respuesta para ese caso es $433$ pero no tengo ni idea de lo que hay que hacer para un mayor $n$ . Incluso consiguiendo el número de formas para $n=5$ parece muy difícil.

Y, antes de que alguien pregunte, este problema salió de mi cabeza, no de un libro ni nada por el estilo, así que no tengo ninguna pista de cómo se puede encontrar esto.

Gracias.

Answer 1

Esto no es una respuesta, sino una nota sobre cómo calcular el número de formas $\mathcal{N}_n$ para $n = 5$ .

Podemos dividir el $5\times 5$ tablero en $8$ triángulos en ángulo recto. Rotulemos los estados de uno de los triángulos como sigue:

$$\begin{array}{|ccccc|} \hline * & * & * & * & e\\ * & * & * & c & d\\ * & * & 0 & a & b\\ * & * & * & * & *\\ * & * & * & * & *\\ \hline \end{array}$$

Es fácil comprobar, dada la restricción, que hay

• 5 posibilidades para $\verb/ab/$ - $00, 01, 10, 11, 12$ .
• 12 posibilidades para $\verb/ce/$ - $00, 01, 02, 10, 11, 12, 13, 20, 21, 22, 23, 24$ .

Dada cualquier combinación legal de $a, b, c, e$ el número de posibilidades de $d$ puede ser contar por fuerza bruta. El resultado se resume en la siguiente tabla. $$\begin{array}{r|lllll} & & & \verb/ab/ & & \\ \verb/ce/ & 00 & 01 & 10 & 11 & 12\\ \hline 00 & 2 & 2 & 2 & 2 & 1\\ 01 & 2 & 2 & 2 & 2 & 1\\ 02 & 1 & 1 & 1 & 1 & 1\\ 10 & 2 & 2 & 2 & 2 & 1\\ 11 & 2 & 3 & 2 & 3 & 2\\ 12 & 1 & 2 & 1 & 2 & 2\\ 13 & 0 & 1 & 0 & 1 & 1\\ 20 & 0 & 0 & 1 & 1 & 1\\ 21 & 0 & 0 & 1 & 2 & 2\\ 22 & 0 & 0 & 1 & 2 & 3\\ 23 & 0 & 0 & 0 & 1 & 2\\ 24 & 0 & 0 & 0 & 0 & 1\\ \end{array}$$

Para los otros 7 triángulos, está claro que cada uno de ellos tiene un conjunto similar de posibilidades. Si elegimos 8 configuraciones admisibles, una para cada uno de los 8 triángulos y las pegamos. Podemos construir una configuración legal para todo el tablero siempre que las configuraciones de los triángulos coincidan en sus límites.

Una consecuencia de esto es que si definimos $M_5$ como el $12\times 5$ matrices con entradas en la tabla anterior, el número total de formas de $n = 5$ ¡puede ser evaluado como un rastro!

$$\mathcal{N}_5 = \text{Tr} \left( (M_5^T M_5 )^4 \right) = 178383613 $$

Como doble comprobación, para el caso más fácil $n = 3$ , el correspondiente $M_3$ tiene entradas dadas por la tabla:

$$\begin{array}{r|rl} & \quad\rlap{\verb/ a/} & \\ \verb/c/ & 0 & 1\\ \hline 0 & 1 & 1\\ 1 & 1 & 1\\ 2 & 0 & 1 \end{array} $$ Esto lleva a $$\mathcal{N}_3 = \text{Tr}\left( \begin{bmatrix}1 & 1 & 0\\1 & 1 & 1\end{bmatrix} \begin{bmatrix}1 & 1\\1 & 1\\0 & 1\end{bmatrix} \right)^4 = \text{Tr}\begin{bmatrix}2 & 2\\ 2 & 3\end{bmatrix}^4 = 433 $$ como se esperaba.

Notas

• Esta forma de contar $\mathcal{N}_n$ se inspira en la técnica general Método de la matriz de transferencia para resolver problemas de mecánica estadística. La clave es dividir la configuración en unidades similares entre sí. Calcular las posibilidades de las unidades individuales y representarlas como matrices. Por último, convertir la suma original en la traza del producto de estas matrices.