Tamaño de una $3$ -rejilla cuadrada coloreada para producir un rectángulo monocromático

Question

Dada una cuadrícula cuadrada, de dimensión $k\times k$ ¿Qué tamaño tiene $k$ tienen que ser para que un $3$ -la coloración siempre producirá un rectángulo monocromático -un conjunto de unos cuatro puntos de la cuadrícula del mismo color en un rectángulo alineado con los ejes de la cuadrícula?

(Habrá un rectángulo monocromático cuando, para alguna elección de $a,b,c,d\in \big[1,k\big]$ con $a\neq b$ y $c\neq d$ Todos los puntos $(a,c),(a,d),(b,c),(b,d)\,$ tienen el mismo color).

---

Esto es una continuación de Cada punto de una cuadrícula está coloreado en azul, rojo o verde. Cómo demostrar que existe un rectángulo monocromático? , donde a $3$ -color $4\times 19$ se muestra para contener un rectángulo monocromático, por lo que ya sabemos $k\le 19$ .

Mi trabajo actual muestra $k\le 12$ pero creo que el límite de $k$ puede ser menor.

${\large k\le 12}$
Para cada columna tenemos un número de puntos de cuadrícula de cada color presente. Esto produce un número de pares de colores coincidentes. El número mínimo de estos pares en una columna en un $12\times 12$ se consigue cuando el recuento de los diferentes colores es $(4,4,4)$ dando $\binom 42+\binom 42+\binom 42=18$ pares. En $12$ columnas tendremos al menos $12\times 18=216$ pares de rejillas de colores emparejados. Hay $\binom {12}{2} = 66$ posibles posiciones de la pareja y con la posibilidad de elegir $3$ colores $3\times 66= 198$ diferentes combinaciones de color/par. Claramente con al menos $216$ emparejamientos en un $12\times 12$ $3$ -color debe haber un emparejamiento de colores entre las columnas y, por tanto, un rectángulo monocromático.

---

¿Puede mejorar este límite?

Answer 1

Con $k=11$ Su argumento casi funciona, pero se puede guardar: Cada columna tiene al menos ${4\choose 2}+{4\choose 2}+{3\choose 2}=15$ pares monocromos, por lo que hay al menos $11\times 15=165$ pares monocromos en todas las columnas juntas. Si alguno de los ${11\choose 2}=55$ pares de hileras contenían más de tres pares de este tipo, habríamos terminado. Como $55\cdot 3=165$ Todos los límites encontrados deben ser agudos, es decir:

• En cada columna, un color aparece exactamente tres veces y cada uno de los otros dos colores aparece exactamente seis veces
• Cada uno de los $55$ pares de filas contiene exactamente un par monocromo de cada color

Según el primer punto, cada color aporta un múltiplo de tres de pares, lo que contradice el segundo punto.

Answer 2

Aquí hay una $10 \times 10$ ejemplo sin rectángulo monocromático, si mi programación es correcta:

$$\matrix{1 & 2 & 1 & 2 & 0 & 1 & 0 & 1 & 2 & 0\cr 2 & 1 & 0 & 2 & 2 & 0 & 0 & 1 & 0 & 1\cr 2 & 2 & 1 & 1 & 0 & 2 & 1 & 0 & 0 & 2\cr 2 & 0 & 0 & 0 & 0 & 1 & 1 & 2 & 2 & 1\cr 0 & 0 & 2 & 2 & 1 & 2 & 1 & 1 & 0 & 0\cr 2 & 0 & 2 & 1 & 1 & 0 & 2 & 0 & 1 & 1\cr 0 & 1 & 1 & 2 & 0 & 0 & 2 & 2 & 1 & 2\cr 0 & 1 & 2 & 0 & 1 & 1 & 0 & 0 & 2 & 2\cr 1 & 1 & 0 & 1 & 2 & 2 & 2 & 0 & 2 & 0\cr 1 & 2 & 2 & 0 & 2 & 0 & 1 & 2 & 1 & 0\cr }$$

(versión en color:)