Russia (2000) contest:Prove the existence of a pair of rows and columns with intersections differently coloured

Let the colors used be $A$, $B$, $C$, $D$. We call an unordered pair of squares neoliberal if the two squares lie in the same row and are of different colors. Every row gives rise to $6 \cdot 25^2$ neoliberal pairs (given by $\binom{4}{2}$ possible pairs of colors and $25$ squares of each color). Thus, summing over all the rows, there is a total of $100 \cdot 6 \cdot 25^2$ neoliberal pairs. On the other hand, each such pair is simply the intersection of one row with a pair of distinct columns. Because there are$$\binom{100}{2} = 100 \cdot 99/2$$pairs of columns, some pair of columns contains at least$${{100 \cdot 6 \cdot 25^2}\over{100 \cdot 99/2}} = {{2 \cdot 6 \cdot 25^2}\over{99}} > {{12 \cdot 25^2}\over{4 \cdot 25}} = 75$$neoliberal pairs. Thus, some two fixed columns form neoliberal pairs in at least $76$ rows. We henceforth ignore all other rows and columns; we may as well assume that we have only a $76 \times 2$ board colored in four colors, in which each row contains two different colors and no color occurs more than $25$ times in each column.

For each row, consider the pair of colors it contains. If the pairs $\{A, B\}$ and $\{C, D\}$ each occur in some row, we are done; likewise for $\{A, C\}$, $\{B, D\}$ and $\{A, D\}$, $\{B, C\}$. Thus, suppose that at most one pair of colors from each of these three sets occurs; we now seek a possible relabelling of colors: either $\{A, B\}$, $\{A, C\}$, $\{A, D\}$ are the only pairs that can occur, or $\{A, B\}$, $\{A, C\}$, $\{B, C\}$ are. In the first case, each of the $76$ rows contains a square of color $A$, implying that one column has more than $25$ squares of color $A$, a contradiction. In the second case, each column can contain only the letters $A$, $B$, $C$. There can only be $25$ squares of each color $A$, $B$, $C$ in each column, for a total of at most $150$ squares, but there are $152$ squares in total, a contradiction. This completes the proof.

You already proved the existence of a column-pair such that $76$ of its rows contains different colored square pairs. Four different colored squares that you're looking for is actually in this column-pair:

Number the colors as $0$, $1$, $2$ and $3$. Aforementioned $76$ rows can only have six different pairs: $A=\{0,1\}$, $A'=\{2,3\}$, $B=\{0,2\}$, $B'=\{1,3\}$, $C=\{0,3\}$ and $C'=\{1,2\}$. We assume none of the letters contained in this column-pair with its pair; that is, $A$ and $A'$, $B$ and $B'$, $C$ and $C'$ doesn't belong together in this column-pair (otherwise there is nothing to prove). Since there are $152$ squares and one color can only appear maximum $50$ times in this column-pair, by pigeonhole principle, every color must exist in this column-pair. However, this means that, one color must exist in all rows: For example: If column-pair contains $A$ and $B$, it must contain $C$ (because only $C$ includes color $3$), making color $0$ appear in all rows; if column-pair contains $A$ and $B'$, it must contain $C'$ (because only $C'$ includes color $2$), making color $1$ appear in all rows. Therefore one color appears $76$ times, which is a contradiction.