¿Cuántos colores son necesarios para una red infinita de color para que no sqaure tienen el mismo color en los 4 vértices?

Question

Supongamos que en una red infinita de 2 dimensión, todos los nodos o equivalente, todas las %#% puntos de #%, donde $(p,q)$, necesita ser pintado con un color.

¿Hay alguna forma que, dado bastantes clases de paiting colores, por ejemplo, $p, q \in \mathbb Z$, sqaures todos tendrán al menos 2 colores? ¿es decir que podemos evitar para cualquier cuadrado todos sus 4 vértices están pintadas del mismo color?

¿O... esta imposible?

Answer 1

Solución para rectángulos (ahora retirado de la pregunta): En un infinito de cuadrícula, se requiere un número infinito de colores. Ver la nota de cierre en Cada punto de la cuadrícula es de color azul, rojo o verde. Cómo probar que existe un monocromática rectángulo? dando el tamaño de una cuadrícula necesarios para producir un rectángulo para $n$ colores:

---

Para $n$ colores, utilizando el mismo enfoque, se podría adoptar una cuadrícula de $(n+1)$ filas y, a continuación, requieren $n{n+1 \choose 2}+1 = n(n+1)n/2 +1 = (n^3+n^2)/2 + 1$ columnas para encontrar un rectángulo con el mismo color de las esquinas.

---

---

Trabajo en mono plazas:

Mientras que los números son demasiado grandes para un cómodo imaginación, estas notas de Gasarch (enlace) da una dirección para inferir la existencia de un monocromo de cuadrícula alineado a la plaza en una lo suficientemente grande 2 - o 3-color de la cuadrícula.

---

Una de las piezas clave de la prueba en la que el papel requiere una gran cuadrícula de garantizar la existencia de un mono de color $L$ (tres puntos del mismo color en la forma de un $L$: $(x,y),$ $(x+d,y),$ $(x,y+d)$). Yo quería mejorar en esto, al menos durante dos colores y creo que el proceso puede solicitar más:

Considerar la parte superior izquierda a la inferior derecha de la diagonal de una de dos colores que se $n\times n$ cuadrícula.

Si hay tres regularmente espaciados puntos del mismo color en esta diagonal, hay un mono $L$ en la cuadrícula. Prueba: Considerar los puntos que forman una $L$ con cada posible par de estos tres puntos. Si uno de estos es el color, que es un mono $L$. Si los tres son el color opuesto, forman un mono $L$ en el color opuesto.

Cómo de largo de una diagonal qué necesitamos la fuerza de tres regularmente espaciados puntos del mismo color? Experimentalmente la respuesta es $9$, forzado a partir de los siguientes patrones (mostrado en rojo):

$\mathtt {\color{red}{OOXO}OXX?}$
$\mathtt {\color{red}{OOXX}OOX?X}$
$\mathtt {\color{red}{OXOO}XOXX?}$
$\mathtt {\color{red}{OXOX}XOXO?}$
$\mathtt {\color{red}{OXX}OOXXO?}$

En cada caso el $\mathtt{?}$ crea un regularmente espaciados triplete si lleno de $\mathtt{O}$ o $\mathtt{X}$.

Por lo tanto, cualquier 2 colores $9\times 9$ cuadrícula contiene un mono $L$, la mejora de la anterior, el papel del requisito de obtener un $1539\times 1539$ cuadrícula para esta condición.

A fuerza de un mono-$L$ en tres colores de cuadrícula por la misma técnica que por lo tanto se necesita $10$ regular espaciado de los puntos de la diagonal, la creación de una escasa inferior a la mitad de la cuadrícula de un tamaño adecuado para forzar una $L$ en el resto de los dos colores. No estoy seguro de lo grande que iba a ser, pero de nuevo no debe ser menor que la correspondiente tamaño de la cuadrícula en el papel ($\approx 3^{3^{34}}$).

---

Otra observación: la diagonal de secuencias $\mathtt {OOXOO}$, $\mathtt {OOXXOO}$, o $\mathtt {OXOOXO}$ también producirá un mono$L$, debido a los pares del mismo colores en el mismo espacio. Efectivamente los tres uniformemente espaciados coincidencia de colores es un caso especial de estas, donde el punto central tiene una doble función a la izquierda y a la derecha. Así, la mínima longitud de la diagonal de garantizar un mono $L$ trata $8$:

$\mathtt {\color{red}{OOXO}XX?}$
$\mathtt {\color{red}{OOXX}OXO?}$
$\mathtt {\color{red}{OXOO}XX?}$
$\mathtt {\color{red}{OXOX}XOO?}$
$\mathtt {\color{red}{OXX}OO?X}$

---

Algunas referencias para resolver partes de este problema:
En Monocromático Subconjuntos De Una Cuadrícula Rectangular - $5{\times} 5$ 2-color de la cuadrícula debe tener un mono $L$.
Extremal matrices binarias sin constante 2-plazas - $15{\times} 14$ 2-color de la cuadrícula debe tener un mono plaza