Colores mínimos necesarios para colorear$\mathbb Z^2$ con restricción de subconjuntos conectados

Question

¿Cuál es el número mínimo de colores necesarios para colorear cada unidad cuadrada de$\mathbb Z^2$ de modo que si se coloca cualquier polyomino de orden$n$ en cualquier parte de la cuadrícula, tendría todos sus cuadrados unitarios colocados en cuadrados de diferente ¿colores?

Answer 1

Por extraño $n$, la respuesta es $(n^2+1)/2$.

Para ver que este número es necesario, considere la posibilidad de un diamante en forma de parche de $(n^2+1)/2$ plazas. Todos ellos están dentro de una distancia de $n-1$ de cada uno de los otros, y por lo tanto todos deben tener colores diferentes.

Para ver que este número es suficiente, considere la coloración $x+ny\,\bmod\,{(n^2+1)/2}$. Equicoloured cuadrados dentro de una fila se $(n^2+1)/2\ge n$ aparte. Equicoloured plazas en filas consecutivas, se $n+1$ aparte, y esta aumenta hasta que la progresión se envuelve alrededor y se acerca a $0$ nuevo. Esto sucede en $\Delta y=(n\pm1)/2$, y las distancias correspondientes son

$$\frac{n\pm1}2+\left|\frac{n^2+1}2-\frac{n(n\pm1)}2\right|=\frac{n\pm1}2+\frac{n\mp1}2=n\;.$$

El próximo envolvente se produce en $\Delta y=n$, y, a continuación, la distancia en el $y$ dirección ya es suficiente.

Incluso para $n$, la respuesta es $n^2/2$.

Para ver que este número es necesario, considere la posibilidad de un diamante en forma de parche de $n^2/2-n+1$ de las plazas y de desplazamiento a la derecha por uno para agregar otro $n-1$ cuadrados, para un total de $n^2/2$. Las plazas de esta forma, todos están a una distancia de $n-1$ de cada uno de los otros, y por lo tanto todos deben tener colores diferentes.

Para ver que este número es suficiente, considere la coloración $x+(n-1)y\,\bmod\,n^2/2$. Equicoloured cuadrados dentro de una fila se $n^2/2\ge n$ aparte. Equicoloured plazas en filas consecutivas, se $n$ aparte, y esta aumenta hasta que la progresión se envuelve alrededor y se acerca a $0$ nuevo. Esto sucede en $\Delta y=n/2$, donde la distancia es de $n/2+n^2/2-(n-1)n/2=n$ y a las $\Delta y=n/2+1$, donde la distancia también es $n/2+1+(n-1)(n/2+1)-n^2/2=n$. El próximo envolvente se produce en $\Delta y=n+1$, y, a continuación, la distancia en el $y$ dirección ya es suficiente.