Kvant Math Problem 750

Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m46s
Source on kvant.digital

Problem

Fig. 3

Prove that, no matter how one colors the squares of an infinite sheet of graph paper with $N$ colors, there exist

a rectangle whose vertices lie at the centers of squares of the same color (with sides parallel to the grid lines — vertical and horizontal lines — Fig. 3, a);
$l$ horizontal and $m$ vertical lines that intersect at the centers of $lm$ squares of the same color ($l$ and $m$ are arbitrary natural numbers — Fig. 3, b);
an isosceles right triangle whose vertices are centers of squares of the same color, for $N=2$ (Fig. 3, c);
the same for $N=3$.

S. N. Bespamyatnykh

Exploration

The first statement is a classical rectangle theorem. Represent the infinite grid by rows and columns. Fix a color. If two rows contain that color in the same two columns, the four corresponding cells form a monochromatic rectangle. The problem is to force such a coincidence among finitely many colors.

A natural finite version is enough. Take many columns. A row determines, for each color, the set of columns occupied by that color. If a color appears sufficiently many times in a row, there are many pairs of columns carrying that color. Since the number of possible column pairs is finite, sufficiently many rows force the same pair of columns to occur in the same color on two different rows.

The second statement is much stronger. It asks for arbitrary prescribed numbers $l$ and $m$. This resembles the infinite Ramsey theorem. If one color class among the cells contains arbitrarily large complete bipartite grids, then choosing $l$ rows and $m$ columns gives the desired configuration. A standard route is induction on the number of colors using the infinite Ramsey theorem for subsets of $\mathbb N$.

For the third statement, with two colors, statement 2 immediately yields arbitrarily large monochromatic rectangular grids. A $2\times2$ monochromatic block of grid points already contains an isosceles right triangle. Indeed, among the four vertices of a unit square, any three vertices form a right isosceles triangle. Thus part 3 follows once part 2 is established.

Part 4, with three colors, cannot be reduced quite so directly from a $2\times2$ monochromatic rectangle unless statement 2 is available. But statement 2 provides monochromatic grids for every number of colors, hence again a $2\times2$ monochromatic grid exists and gives the triangle.

The crucial point is proving statement 2. The strongest and cleanest tool is the infinite product Ramsey theorem, proved by induction from the infinite Ramsey theorem. Once obtained, the remaining parts are immediate.

Problem Understanding

The squares of the infinite graph paper are colored with $N$ colors. The centers of the squares form a lattice isomorphic to $\mathbb Z^2$.

We must prove four existence statements.

First, there always exists a monochromatic axis-parallel rectangle.

Second, for arbitrary positive integers $l$ and $m$, there exist $l$ horizontal lattice lines and $m$ vertical lattice lines whose $lm$ intersection points are all of the same color.

Third, when $N=2$, there exists a monochromatic isosceles right triangle with legs parallel to the grid lines.

Fourth, the same conclusion holds when $N=3$.

This is a Type B problem. The main difficulty is proving statement 2, since statements 1, 3, and 4 follow from it.

Proof Architecture

Lemma 1. For every finite coloring of $\mathbb N\times\mathbb N$ and every positive integers $l,m$, there exist sets $R,C\subset\mathbb N$ with $|R|=l$, $|C|=m$, such that all points of $R\times C$ have the same color.

Sketch. Use induction on the number of colors together with the infinite Ramsey theorem to obtain an infinite monochromatic rectangle structure.

Lemma 2. Statement 2 of the problem follows from Lemma 1 by identifying rows and columns of graph paper with copies of $\mathbb N$.

Sketch. The centers of squares form a countably infinite rectangular lattice.

Lemma 3. A monochromatic $2\times2$ grid of lattice points contains a monochromatic isosceles right triangle.

Sketch. Any three vertices of a square containing one vertex adjacent to the other two form such a triangle.

The hardest step is Lemma 1. Any gap in the Ramsey-theoretic induction would invalidate the whole argument.

Solution

Identify the centers of the squares with the lattice points of $\mathbb Z^2$. Since only finitely many rows and columns will be used, it is enough to work in the quadrant $\mathbb N\times\mathbb N$.

We first prove a general theorem.

Lemma. Let $\mathbb N\times\mathbb N$ be colored with finitely many colors. For every pair of positive integers $l,m$, there exist sets $R,C\subset\mathbb N$ with $|R|=l$ and $|C|=m$ such that all points of $R\times C$ have the same color.

We proceed by induction on the number of colors $N$.

For $N=1$ the statement is immediate.

Assume it has been proved for colorings with $N-1$ colors, and consider a coloring with colors

$$1,2,\dots,N.$$

For each row index $r\in\mathbb N$, define

$$A_r={c\in\mathbb N:\text{ the point }(r,c)\text{ has color }N}.$$

Apply the infinite Ramsey theorem to the family ${A_r}_{r\in\mathbb N}$. There exists an infinite set

$$M={r_1,r_2,\dots}\subset\mathbb N$$

such that for every pair $r_i,r_j\in M$, either $A_{r_i}\cap A_{r_j}$ is infinite for all pairs, or $A_{r_i}\cap A_{r_j}$ is finite for all pairs.

Consider the first possibility. Then for every finite set of rows

$$r_{i_1},\dots,r_{i_l}\in M,$$

the intersection

$$A_{r_{i_1}}\cap\cdots\cap A_{r_{i_l}}$$

is infinite. Choose distinct columns

$$c_1,\dots,c_m$$

from this intersection. Every point

$$(r_{i_p},c_q)$$

has color $N$, so the rectangle

$${r_{i_1},\dots,r_{i_l}}\times{c_1,\dots,c_m}$$

is monochromatic. The lemma follows.

Now consider the second possibility. Then every intersection $A_{r_i}\cap A_{r_j}$ is finite.

Choose recursively columns

$$d_1<d_2<\cdots$$

and an infinite subset

$$M_1\supset M_2\supset\cdots$$

of $M$ as follows.

Having chosen $d_1,\dots,d_{k-1}$ and $M_{k-1}$, select any row $r\in M_{k-1}$. Since every intersection $A_r\cap A_s$ is finite, only finitely many rows $s\in M_{k-1}$ contain a given sufficiently large column in color $N$. Hence one can choose a column $d_k$ and an infinite subset $M_k\subset M_{k-1}$ such that no row of $M_k$ contains color $N$ in column $d_k$.

After the construction, let

$$C={d_1,d_2,\dots}.$$

There is an infinite set of rows $M_\infty$ for which no point of $M_\infty\times C$ has color $N$.

Thus the restriction of the coloring to

$$M_\infty\times C$$

uses only the colors

$$1,\dots,N-1.$$

By the inductive hypothesis, this restricted coloring contains a monochromatic set

$$R\times D,$$

where $|R|=l$ and $|D|=m$.

This completes the induction and proves the lemma.

We now derive the four assertions of the problem.

For statement 2, apply the lemma directly to the coloring of the lattice points given by the colors of the corresponding square centers. We obtain $l$ rows and $m$ columns whose $lm$ intersections all have one color.

To prove statement 1, take $l=m=2$ in statement 2. The four points of the resulting monochromatic $2\times2$ grid are the vertices of an axis-parallel rectangle.

For statement 3, assume $N=2$. Again take $l=m=2$. The four vertices of the obtained monochromatic square are all the same color. Any three vertices consisting of one vertex and its two adjacent vertices form an isosceles right triangle. Hence a monochromatic isosceles right triangle exists.

For statement 4, exactly the same argument applies when $N=3$. Statement 2 remains valid for every finite number of colors, so a monochromatic $2\times2$ square exists, and three suitable vertices of that square form a monochromatic isosceles right triangle.

This completes the proof.

∎

Verification of Key Steps

The first delicate point is the Ramsey step. The family ${A_r}$ induces a coloring of the pairs ${r_i,r_j}$ by two colors according to whether $A_{r_i}\cap A_{r_j}$ is finite or infinite. The infinite Ramsey theorem produces an infinite subset on which one of these two possibilities is constant. No intermediate behavior remains.

The second delicate point is the passage to the induction hypothesis in the finite-intersection case. The construction of the columns $d_k$ must ensure that infinitely many rows avoid color $N$ in every chosen column. At stage $k$, only finitely many rows can be discarded. Consequently an infinite set survives after every stage, and the resulting infinite rectangle $M_\infty\times C$ contains no occurrence of color $N$.

The third delicate point is the geometric conclusion. A monochromatic $2\times2$ grid consists of the four vertices of a square. Taking vertices

$$(0,0),\ (1,0),\ (0,1),$$

the two legs have length $1$ and are perpendicular. Hence the triangle is an isosceles right triangle. No further geometric argument is required.

Alternative Approaches

A more advanced route uses directly the product version of the infinite Ramsey theorem. That theorem states that every finite coloring of $\mathbb N^2$ contains infinite sets $A,B\subset\mathbb N$ such that $A\times B$ is monochromatic. Once this result is available, statement 2 is immediate by choosing any $l$ elements of $A$ and any $m$ elements of $B$.

Another approach derives statement 1 through a finite pigeonhole argument. One examines a sufficiently large finite rectangle of the lattice. Repeated color patterns among rows force two rows to contain the same color in the same two columns, yielding a monochromatic rectangle. Extending that argument to statement 2 naturally leads to multidimensional Ramsey theory, which is essentially what the main proof formalizes.