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

We have a $100\times100$ board divided into $10^4$ unit squares. These squares are coloured with four colours so that every row and every column has $25$ squares of each colour. Prove that there are $2$ rows and $2$ columns such that their $4$ intersections are painted with different colors.

My attempt:

I first counted number of pairs $\mathcal P$ $(r_1,r_2)$ such that $r_1,r_2$ belongs to same row, but different in colour. This can be done in $$\binom 42\times25\times 25$$ ways. So, in $100$ rows, this number is $$100\times\binom 42\times25\times 25$$ Now, we can find a pair of columns in $$\binom{100}2$$ ways.

So, by Pigeonhole Principle, we can find at least a pair of columns containing $$\left\lceil\frac{100\times\binom 42\times25\times 25}{\binom{100}2}\right\rceil\\=\left\lceil\frac{100\times75\times 50}{50\times99}\right\rceil\\=76$$ of those pairs $\mathcal P$.

But unable to proceed anymore. And this approach too seems misleading, because in every pair of columns, we can always find $\binom42\times25\times25$ pairs from $\mathcal P$. So, this approach makes no sense, I think.

What should be correct approach? And also, "if we pour $nk+1$ objects into $n$ urns, then there is an urn with $k+1$ objects", can this concept be plugged in this question?

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.