Demostrar que existe una intersección de cuatro colores en una $100×100$ rejilla

Question

A $100×100$ La rejilla está coloreada con cuatro colores. Hay exactamente 25 bloques de cada color en cada fila y columna. Demuestra que existe una intersección entre dos filas y columnas tal que los cuatro bloques que se cruzan tienen colores diferentes.

Estoy tratando de demostrar esto usando la invariancia. Pero no sé cómo proceder. Tampoco sé si este es el enfoque correcto por lo que cualquier idea es apreciada:)

Answer 1

Observe que hay $\binom{4}{2} \cdot 25^2$ pares de colores diferentes en cada fila, por lo que hay $100 \cdot \binom{4}{2} \cdot 25^2$ pares de colores diferentes que están en la misma fila en total. Ahora, observe que $100 \cdot \binom{4}{2} \cdot 25^2 > 75 \cdot \binom{100}{2}$ . Entonces, por el principio de encasillamiento generalizado, hay dos columnas con $>75$ pares de colores diferentes que están en la misma fila. Digamos que hay 76 pares de colores diferentes que están en la misma fila. Digamos que los nombres de los colores son del conjunto $\{0,1,2,3\}$ . Ahora bien, si la afirmación no es cierta, entonces $\{0,1\}$ , $\{0,2\}$ , $\{0,3\}$ o $\{0,1\}$ , $\{0,2\}$ , $\{1,2\}$ son los posibles pares que podemos utilizar para cubrir estos $2$ columnas (WLOG). El primer caso es claramente imposible ya que tenemos un límite de $25$ para cada color, y el segundo caso es imposible ya que $3$ colores no son suficientes para cubrir un total de $76 \cdot 2=152$ bloques. Así que la afirmación es cierta.

Editar: Si no puedes entender lo que quiero decir con "pares de colores diferentes que están en la misma fila", mira los comentarios más abajo de @Mike.