¿Cuántos colores es necesario para que un rectángulo no cubra siempre más de una vez?

Question

Si tenemos una infinita red, y hemos de color de cada celda, cantidad de colores que hacen que se necesita para que un $m \times n$ rectángulo siempre cubre a más de 1 de cada color no importa cómo se coloca? (La rotación del rectángulo es permitido.)

Debe tener al menos $mn$, pero parece $mn$ no es siempre suficiente.

Conocer los resultados:

1. Para $m \times 1$, la respuesta es $m$.
2. Para $m \times m$ es $m^2$.

Aquí son los datos de un programa de ordenador. Tenga en cuenta que mi programa sólo considera periódico colorantes fundamentales en la región de la misma área como el número de colores. Así que es posible que los colores con menos colores son posibles si ellos no están organizadas de esta manera.

La siguiente tabla muestra $k - mn$, donde $k$ es el número de colores necesarios. El patrón parece obvio ahora (aunque una prueba de que aún es necesario).

Un par de conjeturas:

• Para todos los casos en la tabla, si $mn$ no es suficiente, entonces se ve como $mn + m$ es de $m < n$. (Falsa. resulta que esto no es cierto; $6 \times 4$ parece requerir de 32 colores. He actualizado la tabla de arriba.)
• Desde mi construcciones se parece a $mn$ puede ser suficiente una vez $m$ es lo suficientemente grande para que fija $n$ (y viceversa). Esto es consistente con la forma rectangular apuntados trabajo. (Parece Falso.)
• De Gregorio, J. Puleo comentario: Si $m$ divide $n$, es plausible que la $mn$ es suficiente. (Si $m$ divide $n$, podemos considerar el rectángulo de una barra de cuadros grandes, por lo que mediante la combinación de 1. y 2. desde arriba podemos ser capaces de demostrar esto.) (Verdadera. Ver su respuesta.)
• Para $m \times (m + 1)$, el programa encuentra el uso de colorantes $m(m + 2)$ colores. La fundamental región puede ser descrito por un paralelogramo con dos lados adyacentes $(m(m + 2), 0)$ e $(m + 1, 1)$. Estas plazas están marcadas en amarillo en la primera tabla. Edit: De hecho, para los rectángulos representado por una célula blanca que parece que para $m \times (m + k)$ necesitamos $m(m + 2k)$ colores.
• Parece que para $m \times n$ donde $n = jm, jm - 1, jm - 2, \cdots, \lfloor\frac{m + 2}{2}\rfloor$ y todos los $j$, tenemos $jm^2$ colores. Estas plazas están marcadas en verde en la primera tabla.

¿Alguien sabe en general de la cantidad de colores que necesitamos?

---

De fondo , Mientras que tratando de encontrar todos los libres de fallos apuntados de la P-pentomino, me di cuenta de que podemos demostrar que el P-pentomino no azulejo cualquier $5 \times n$ rectángulo extraños $n$, debido a que un rectángulo no encaja $n$ $2 \times 2$ plazas, y para ello también puede no encajar $n$ P-pentominoes. Esto me hizo preguntarme cómo nos puede venir generalmente para baldosas un rectángulo con un arbitrario rectángulo determinado.

En general, los rectángulos pack y azulejo en formas complicadas, por lo que un análisis directo parece demasiado duro. (Por ejemplo, podemos colocar 4 $2 \times 3$ rectángulos en un $5 \times 5$ rectángulo en un molinillo de baldosas de la construcción). Entonces yo, sin embargo, de extender esta técnica para encontrar cuántos rectángulos se va a montar. Pero eso sólo funciona si tenemos $mn$ colores para un $m \times n$ rectángulo... y cuando descubrí este no es siempre el caso, me preguntaba ¿cuál es la regla general.

Answer 1

Yo no he desarrollado exactamente cómo usar esto, pero creo que la idea que se debe , probablemente, suficiente para, al menos, demostrar que $mn$ colores suficiente si y sólo si $m$ divide $n$: si dos plazas se encuentran en la misma fila o en la misma columna y son exactamente $n$ plazas, aparte de esa fila o columna, a continuación, ambas deben tener el mismo color. Tenga en cuenta que dado que no intervenir plazas en esa fila o columna también pueden tener el mismo color, esto significa que cada fila y cada columna es básicamente de color de forma periódica, con período de $n$. Así que creo que una de colorear con $mn$ colores se especifica completamente por sus valores en un $n \times n$ plaza.

Prueba: Supongamos que $m < n$ y supongamos que tenemos un colorante de uso de $mn$ colores, y considere la posibilidad de $(m+1)$ por $(n+1)$ rectángulo, como se muestra a continuación:

Digamos que el color en la esquina superior izquierda es de color púrpura. Todos los colores de la izquierda $n$ columnas de la fila superior se llama "tonos de rojo", y todos los colores en la parte superior $m$ columnas de la columna de la izquierda se llama "shades of blue", representado por el sombreado de luz en el diagrama. Púrpura es una sombra de rojo y con un tono de azul.

Cuando nos movemos hacia abajo en la fila $m+1$, los únicos colores disponibles para la izquierda $n$ columnas son los tonos de rojo. Además, como $m < n$, a la izquierda de la plaza en la fila $m+1$ no puede ser de color púrpura, ya que esto causaría un rectángulo vertical con la misma esquina superior izquierda tiene dos plazas de color púrpura. Con sólo los tonos de rojo disponible para esa fila, púrpura debe aparecer en algún otro lugar entre el extremo izquierda de la $n$ columnas en la fila $m+1$.

Por otro lado, en la columna $n+1$ sólo podemos utilizar tonos de azul, entre los cuales no debe ser un cuadrado morado. Si el círculo cuadrado ¿ no utilizar el color púrpura, y luego la parte inferior derecha $(m \times n)$ rectángulo tiene dos plazas de color púrpura. De ahí el círculo cuadrado debe ser de color púrpura. Por lo tanto dos plazas en la distancia $n$ a lo largo de la misma fila debe tener el mismo color. Repitiendo el argumento con filas y columnas de intercambiar muestra que dos cuadrados a distancia $n$ a lo largo de una columna tienen el mismo color.

Edit: creo que ahora puedo ver cómo esto implica que si $mn$ colores es suficiente, a continuación, $m$ divide $n$. Supongamos que $m$ no divide $n$, pero tenemos una $mn$colorear. Esta $mn$-colorear está determinada por sus valores en un $n \times n$ plaza. Deje $C_i$ el conjunto de colores que se utilizan en la $i$th fila de esta plaza. Vemos que $C_1, \ldots, C_m$ son disjuntos a pares (estas filas a todos los que estén contenidas en un $m \times n$ rectángulo), y que $C_i = C_{m+i}$ para todos los $i < n-m$, desde el $C_{m+i}$ debe ser disjunta de a$C_{i+1}, \ldots, C_{m+i-1}$, dejando sólo el $n$ colores en $C_i$ disponible. (Fila $m+i$ y la de la fila $i$ podrían tener estos colores en un orden diferente, pero será el mismo conjunto de colores.)

Si $m$ dividido $n$, entonces nos gustaría obtener cada uno de los conjuntos de $C_1, \ldots, C_m$ aparecen exactamente $n/m$ veces en la plaza. Sin embargo, desde la $m$ no divide $n$, este patrón de repetición de conjuntos se "cortan" en la parte inferior, y $C_1$ aparece en algunas fila $C_{n-i}$ para $i < m$. Ahora un rectángulo horizontal a partir de la fila $n-i$ contendrá dos filas de colores con los colores de $C_1$ una vez que la plaza se repite, contradiciendo la hipótesis de que este es un buen colorante.

Answer 2

Wlog asumen $m \le n$.

No tengo una idea clara de cómo probar general los límites inferiores aparte de la obvia ($mn$), por lo que esta es sólo una respuesta parcial. Mi objetivo es proporcionar una constructivo límite superior para la óptima coloración, y tomo nota de que coincide con el primer lugar de la tabla.

Dejaré $F(m, n)$ denotar el número de colores en una óptima coloración por $m \times n$.

Lema: $F(1, n) = n$

Como se indica en la pregunta, y fácilmente demostrado por la coloración $A_{i,j} = (i + j) \bmod n$.

Lema: $F(am, bn) \le ab F(m, n)$

Prueba: se puede tomar en cualquier ordenamiento en teselas para $m \times n$ y dividir cada cuadrado en $a \times b$ plazas más pequeñas, de coloración de acuerdo a un bijection de (cuadrado grande de color, subrow, subcolumn) para el pequeño cuadrado de color.

Corolario: $F(am, an) \le a^2 F(m,n)$.

Corolario: $F(m, m) = m^2$, como también se indica en la pregunta.

Lema: $F(m, n) \le F(m, n+1)$

La prueba: un rectángulo de tamaño $m \times n$ está contenida en un rectángulo con la misma esquina superior izquierda, que es uno más amplio.

Lema: Si $\gcd(m, n) = 1$ entonces $F(m, n) \le m(n + (n \bmod m))$

Supongamos $n = am + b$ con $0 \le b < m$ e $\gcd(m, b) = 1$. Por la identidad de Bézout existen enteros $x, y$ tal que $mx + by = 1$. Deje $k = (ay - 2x)m + 1 = (n+b)y - 1$. Deje $W = m(n+b)$. Tomamos un periódico de mosaico con $A_{i,j} = (ki+j) \bmod W$.

Si tenemos en cuenta los dos rectángulos con la celda superior izquierda $(r_0, c_0)$ se requiere el $mn$de las células de la $(r_0 + \delta_r, c_0 + \delta_c)$, $0 \le \delta_r < m$, $0 \le \delta_c < n$ tener distintos colores; y el $mn$de las células de la $(r_0 + \delta_r, c_0 + \delta_c)$, $0 \le \delta_r < n$, $0 \le \delta_c < m$ tener distintos colores. $(k(r_0 + \delta_r) + (c_0 + \delta_c)) = (kr_0 + c_0) + (k\delta_r + \delta_c)$, por lo que esto se reduce a

1. $k \delta_r + \delta_c \not\equiv 0 \pmod W$ cuando $0 \le \delta_r < m, 0 \le \delta_c < n$ menos $\delta_r = \delta_c = 0$.
2. $k \delta_r + \delta_c \not\equiv 0 \pmod W$ cuando $0 \le \delta_r < n, 0 \le \delta_c < m$ menos $\delta_r = \delta_c = 0$.

Así que la pregunta es para lo $\delta_r, \delta_c$ do tenemos $k \delta_r + \delta_c = uW$? Ampliar: $((n+b)y-1)\delta_r + \delta_c = um(n+b)$o $(n+b)(y\delta_r-um) = \delta_r - \delta_c$. Puesto que el valor absoluto de la RHS es en la mayoría de las $n-1$, esto sólo puede ser cierto cuando se $\delta_r = \delta_c$ e $y \delta_r = um$. Pero $\gcd(m, y) = 1$, por lo que si $m \mid y \delta_r$ entonces $\delta_r = \delta_c = m$, poniendo el celular fuera de los dos rectángulos.

Teorema: $F(m, n) \le m\min\left(n + (n \bmod m), m\left\lceil\frac{n}{m}\right\rceil\right)$

Esto es sólo reunir los diversos lemmata anteriormente, y que coincide con su primera tabla.