Prouvez qu'il existe une intersection à quatre couleurs dans une $100×100$ grille [dupliquer]

Question

UNE $100×100$la grille est colorée avec quatre couleurs. Il y a exactement 25 blocs de chaque couleur dans chaque ligne et colonne. Prouvez qu'il existe une intersection entre deux lignes et colonnes de telle sorte que les quatre blocs qui se croisent ont des couleurs différentes.

J'essaie de prouver cela en utilisant l'invariance. Mais je ne sais pas comment procéder. Je ne sais pas non plus si c'est la bonne approche, donc toutes les idées sont appréciées :)

Answer 1

Notez qu'il y a $\binom{4}{2} \cdot 25^2$ paires de couleurs différentes sur chaque rangée, il y a donc $100 \cdot \binom{4}{2} \cdot 25^2$paires de couleurs différentes qui sont sur la même ligne au total. Maintenant, remarquez que$100 \cdot \binom{4}{2} \cdot 25^2 > 75 \cdot \binom{100}{2}$. Ainsi, selon le principe généralisé du casier, il y a deux colonnes avec$>75$paires de couleurs différentes qui sont sur la même ligne. Disons qu'il y a 76 paires de couleurs différentes qui sont sur la même rangée. Disons que les noms des couleurs proviennent de l'ensemble$\{0,1,2,3\}$. Maintenant, si l'affirmation n'est pas vraie, alors non plus$\{0,1\}$, $\{0,2\}$, $\{0,3\}$ ou $\{0,1\}$, $\{0,2\}$, $\{1,2\}$ sont les paires possibles que nous pouvons utiliser pour couvrir ces $2$colonnes (WLOG). Le premier cas est clairement impossible puisque nous avons une limite de$25$ pour chaque couleur, et le second cas est impossible car $3$ les couleurs ne suffisent pas pour couvrir un total de $76 \cdot 2=152$blocs. Donc, l'affirmation est vraie.

Edit: Si vous ne pouvez pas comprendre ce que j'entends par "paires de couleurs différentes qui sont sur la même ligne", voyez les commentaires ci-dessous de @Mike.