10
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Choose randomly the first row and column, then you have 75 choices for the second row, and then at least one choice for the second column (since at most 49+49 choices share a common colour). Have I misunderstood the problem? $\endgroup$ – Heinrich Apr 10 '16 at 11:50
4
$\begingroup$

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.

$\endgroup$
4
+100
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy