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.