A $100×100$ grid is colored with four colors. There are exactly 25 blocks of each color in every row and column. Prove that there exists an intersection between two rows and columns such that all four intersecting blocks have different colors.
I am trying to prove this using invariance. But I don't know how to proceed. I also don't know if this is the correct approach so any ideas is appreciated:)
Notice that there are $\binom{4}{2} \cdot 25^2$ pairs of different colors on each row, so there are $100 \cdot \binom{4}{2} \cdot 25^2$ pairs of different colors which are on the same row in total. Now, notice that $100 \cdot \binom{4}{2} \cdot 25^2 > 75 \cdot \binom{100}{2}$. So, by the generalized pigeonhole principle, there are two columns with $>75$ pairs of different colors which are on the same row. Say there are 76 pairs of different colors which are on the same row. Say the names of the colors are from the set $\{0,1,2,3\}$. Now, if the claim is not true, then either $\{0,1\}$, $\{0,2\}$, $\{0,3\}$ or $\{0,1\}$, $\{0,2\}$, $\{1,2\}$ are the possible pairs we can use to cover these $2$ columns (WLOG). The first case is clearly impossible since we have a limit of $25$ for each color, and the second case is impossible since $3$ colors are not enough to cover a total of $76 \cdot 2=152$ blocks. So the claim is true.
Edit: If you cannot understand what I mean by "pairs of different colors that are on the same row", see the comments below from @Mike.