Every point of a grid is colored in blue, red or green. How to prove there is a monochromatic rectangle?

Solution 1:

Such a rectangle will occur in a grid of $19$ columns by $4$ rows.

By the pigeonhole principle, each column must have a repeated colour point. Ignoring any later repeats, classify the columns according to the first two repeat colour positions; there are $6$ options: $(1,2), (1,3), (1,4), (2, 3), (2, 4)$ and $(3,4)$. So since there are also $3$ colour options for the repeated colours there are only $6\times3=18$ different options for repeated colour by position. Therefore, by the pigeonhole principle again, in a $19\times 4$ grid we must have a suitable rectangle with identically coloured corners.

From an observation by Pere in comments:

For $n$ colours, using the same approach, we would adopt a grid of $(n+1)$ rows and then require $n{n+1 \choose 2}+1 = n(n+1)n/2 +1 = (n^3+n^2)/2 + 1$ columns to find a rectangle with same-coloured corners.

Solution 2:

For a slightly more quantitative proof, we may show that there is a monochromatic rectangle with its largest dimension being $\color{red}{\leq 82}$ and its smallest dimension being $\color{red}{\leq 4}$.

Step 1. We may give to any integer point $(x,0)$ on the $x$-axis a maxi-color in the set $\{1,2,\ldots,80,81\}$ depending on the actual colors of $(x,0),(x,1),(x,2),(x,3)$.

Step 2. By the Dirichlet box principle, among $82$ consecutive lattice points on the $x$-axis at least two of them, say $(a,0)$ and $(b,0)$, have the same maxi-color.

Step 3. Since we have only three actual colors, at least two points among $(a,0),(a,1),(a,2),(a,3)$ have the same color. Such points, coupled with the corresponding points on $x=b$, give the wanted monochromatic rectangle.

The $82$ above can be replaced by a smaller number, namely $1+\alpha(G)$, i.e. one plus the size of the largest independent set in a quite complicated graph (of the Haggkvist-Hell type) on $81$ vertices. So we may also improve the given bound by using some rather deep results about topological graphs (see Kneser's conjecture, proved by Lovasz in 1978 through the Borsuk-Ulam theorem).

However, an elementary proof that $\alpha(G)=18$ is presented above by Joffan.

Solution 3:

Theorem: Let $X,Y$ be infinite sets. If the points of $X\times Y$ are colored with a finite number of colors in such a way that there exists a set $C$ of $c$ colors such that for every $x\in X$ only colors in $C$ appear an infinite number of times among pairs of the form $(x,y)$, then there exist $x_1,x_2\in X,y_1,y_2\in Y$ so that $(x_1,y_1),(x_1,y_2),(x_2,y_1),(x_2,y_2)$ all have the same color.

Proof:

We proceed by induction on $c$, when $c=1$ it is clear. Take any $x_1,x_2$ and let $\alpha$ be the only color that appears an infinite number of times. Notice that the set of $A_{x_1}=\{y\in Y | (x_1,y) \text{ has color } \alpha\}$ has finite complement, and so does the set $A_{x_2}=\{y\in Y | (x_2,y) \text{ has color } \alpha\}$. This implies $A_{x_1}\cap A_{x_2}$ is infinite. Taking $x1,x2$ and any $y_1,y_2\in A_{x_1}\cap A_{x_2}$ does the trick.

Inductive step: Consider any $x\in X$, there must be an $\alpha \in Y$ such that the set $A_{x}=\{y\in Y | (x,y) \text{ has color } \alpha\}$ is infinite. Now consider the set $X'=X\setminus x$ and $Y'=A_x$. If there is an $x'\in X'$ such that there is an infinite number of $y'\in Y'$ such that $(x',y')$ has color $\alpha$ then we are done. just take $x,x'$ and $y_1,y_2$ such that $(x',y_1)$ and $(x',y_2)$ have color $\alpha$. Otherwise notice that the set $C'=C\setminus\alpha$ has $c-1$ elements, and for every $x\in X'$ the only colors that appear an infinite number of times among the pairs $(x,y)$ are in $C'$. By the inductive hypothesis there exist $x_1,x_2\in X'$ and $y_1,y_2\in Y'$ such that $(x_1,y_1),(x_1,y_2),(x_2,y_1),(x_2,y_2)$ all have the same color.