Square labeled with same number.

Question

Recently I met this combinatorics problem: "Let all points with integer coordinates in a plane be labeled with one of the numbers $1,2,3,...,n$. Prove that there is a rectangle whose vertices are labeled with the same number.

---

The solution makes use of the pigeonhole principle. Let's consider the following set of points $S = \{(i,j) \mid 0\le i \le n^{n+1}; 0 \le j \le n \}$. Every one of the lines $x=i$, where $ 0\le i \le n^{n+1}$ contains $(n+1)$ points from S. The number of such lines is $n^{n+1} + 1$. Now let's consider all points that are in $S$ and lie on one of these lines. Since there are $(n+1)$ dots on the line, at least two of them must be labeled with the same number.

Now since we have $(n+1)$ dots, there are $V_{n}^{n+1} = n^{n+1}$ ways to label the lines. But since we have $n^{n+1} + 1$ such lines, there must be at least two of them that have the same labeling. From the previous claim there are at least 2 same-labeled points on each lines, so there exist points $(i,k_1), (i,k_2), (j,k_1), (j,k_2)$ that are labeled with the same number. Obviously these points are vertices of a rectangle and hence the proof.

I was curious and I tried to prove that we can always find a square, whose vertices are labeled with the same number. I tried to prove it using the same method, but I failed. Since I'm not sure whether this claim holds, I tried to find a labeling that assures us there are no such squares, but again I failed. So is it possible to always find a square, whose vertices are labeled with the same number? If no, is it possible to find a labeling such that there aren't such squares?

Answer 1

There is always a horizontal square, even if you only color the points in the first quadrant of the plane. This is a classical result of Gallai (Grünwald), but tracking down an accessible reference seems tricky. Szemerédi, in his classic 1974 ICM paper, refers to the Gallai result for $2$ colors; Adhikari and Rath quote the result for an arbitrary number of colors, which suffices for your problem:

Fix a finite set $S$ of lattice points in the plane. Then for any coloring of the lattice points in the first quadrant of the plane with $r$ colors, there exists a monochromatic translate of a dilation of $S$. (That is, there are integers $a$ and $b$ such that all of the lattice points in the set $a S + b$ are the same color.)

In particular, take $S$ to be the four corners of a square; then any coloring contains a monochromatic square of some size.

S. D. Adhikari and P. Rath, Monochromatic configurations for finite colourings of the plane, Note di Matematica 22 (1), 2003, p. 59-63.