Prove que existe um cruzamento de quatro cores em uma de quatro cores $100×100$ grade [duplicado]

Dec 27 2020

UMA $100×100$a grade é colorida com quatro cores. Existem exatamente 25 blocos de cada cor em cada linha e coluna. Prove que existe uma interseção entre duas linhas e colunas, de forma que todos os quatro blocos que se cruzam têm cores diferentes.

Estou tentando provar isso usando invariância. Mas não sei como proceder. Eu também não sei se esta é a abordagem correta, então quaisquer ideias são apreciadas :)

Respostas

2 Tan Dec 27 2020 at 05:57

Observe que existem $\binom{4}{2} \cdot 25^2$ pares de cores diferentes em cada linha, então há $100 \cdot \binom{4}{2} \cdot 25^2$pares de cores diferentes que estão na mesma linha no total. Agora, observe que$100 \cdot \binom{4}{2} \cdot 25^2 > 75 \cdot \binom{100}{2}$. Assim, pelo princípio do escaninho generalizado, existem duas colunas com$>75$pares de cores diferentes que estão na mesma linha. Digamos que haja 76 pares de cores diferentes na mesma linha. Diga que os nomes das cores são do conjunto$\{0,1,2,3\}$. Agora, se a afirmação não for verdadeira, então$\{0,1\}$, $\{0,2\}$, $\{0,3\}$ ou $\{0,1\}$, $\{0,2\}$, $\{1,2\}$ são os pares possíveis que podemos usar para cobrir esses $2$colunas (WLOG). O primeiro caso é claramente impossível, pois temos um limite de$25$ para cada cor, e o segundo caso é impossível, pois $3$ as cores não são suficientes para cobrir um total de $76 \cdot 2=152$blocos. Portanto, a afirmação é verdadeira.

Edit: Se você não consegue entender o que quero dizer com "pares de cores diferentes que estão na mesma linha", consulte os comentários abaixo de @Mike.