Demuestre que existe una intersección de cuatro colores en un $100×100$ cuadrícula [duplicado]

Question

UN $100×100$la cuadrícula está coloreada con cuatro colores. Hay exactamente 25 bloques de cada color en cada fila y columna. Demuestre que existe una intersección entre dos filas y columnas de modo que los cuatro bloques que se cruzan tengan colores diferentes.

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

Answer 1

Note que hay $\binom{4}{2} \cdot 25^2$ pares de diferentes colores en cada fila, por lo que hay $100 \cdot \binom{4}{2} \cdot 25^2$pares de diferentes colores que están en la misma fila en total. Ahora, note que$100 \cdot \binom{4}{2} \cdot 25^2 > 75 \cdot \binom{100}{2}$. Entonces, por el principio de casillero generalizado, hay dos columnas con$>75$pares de diferentes colores que están en la misma fila. Digamos que hay 76 pares de colores diferentes que están en la misma fila. Di 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$ los colores no son suficientes para cubrir un total de $76 \cdot 2=152$bloques. Entonces la afirmación es cierta.

Editar: Si no puede entender lo que quiero decir con "pares de diferentes colores que están en la misma fila", vea los comentarios a continuación de @Mike.