# Show that there exists a rectangle such that each of its four vertices are of same colour and its sides are parallel to the X and Y axes.

Question: Let $$n\in\mathbb{N}$$. We colour every lattice point on X-Y plane by one of $$n$$ colours. Show that there exists a rectangle such that each of its four vertices are of same colour and its sides are parallel to the X and Y axes.

Solution: Let us select any consecutive $$n+1$$ lattice points such that the line joining all those points is parallel to the Y-axis. For our ease, let us consider that the vertical line under consideration be $$x=k$$, where $$k$$ is an arbitrary integer and the $$n+1$$ lattice points be of the form $$(k,j+i)$$, where $$j$$ is any arbitrary integer and $$i\in\mathbb{Z}$$, varies from $$i=0$$ to $$i=n$$. Now since, there are $$n$$ colours and we have selected $$n+1$$ lattice points, therefore by the Pigeon-Hole Principle, we can conclude that $$\exists$$ a hole with at least two pigeons, i.e., there exists at least two lattice points having the same colour.

Now, let us consider all the $$n^{n+1}+1$$ vertical lines $$x=k, x=k+1, x=k+2,\cdots ,x=k+n^{n+1}$$ and $$n+1$$ lattice points of the form $$(k+l,j+i)$$ where $$k,j,i$$ has the same meaning as above and $$l\in\mathbb{Z}$$, varies from $$l=0$$ to $$l=n^{n+1}$$.

Now, since there are exactly $$n^{n+1}$$ ways to colour any set of $$n+1$$ lattice points and we have $$n^{n+1}+1$$ line segments having $$n+1$$ lattice points on each of them, therefore, by the Pigeon-Hole Principle we can conclude that $$\exists$$ at least two line segments $$L_1$$ and $$L_2$$ such that they have the same sequence of colouring.

Thus, consider the lines $$L_1$$ and $$L_2$$. Now each of $$L_1$$ and $$L_2$$ has at least two lattice points having the same colour. Let those points on $$L_1$$ be indexed as $$A$$ and $$B$$, such that $$B$$ is located at a higher point $$A$$ and those points on $$L_2$$ be indexed as $$C$$ and $$D$$, such that $$C$$ is located at a higher point than $$D$$. Now since $$L_1$$ and $$L_2$$ has the same sequence of colouring, it directly implies that all of $$A,B,C$$ and $$D$$ has the same colour. Observe that $$ABCD$$ gives us our required triangle, i.e, a rectangle having all of it's vertices of the same colour, such that it's sides are parallel to the X and Y axes.

Is this solution correct and rigorous enough? If yes, is there a better solution?

• What's the source of this question, please? – Gerry Myerson May 13 '20 at 9:29
• @GerryMyerson, I wish I knew the original source. I found this question on a question paper given by my tutor. I'm sorry. :( – Sanket Biswas May 13 '20 at 10:09

To simplify things, suppose our lattice is $$\Bbb Z^2$$, and define $$c:\Bbb Z^2\rightarrow\{1,\ldots,n\}$$ the coloring scheme. The color of a coordinate $$(a,b)$$ is then $$c_{a,b}$$.
First, the function $$\left\{\begin{array}{ccc} \Bbb Z & \rightarrow & \{1,\ldots,n\}^{n+1} \\ k & \mapsto & (c_{k,0},\ldots,c_{k,n}) \end{array}\right.$$ has an infinite domain and a finite image. By the pigeonhole principle, there exist $$i\neq j\in\Bbb Z$$ such that $$(c_{i,0},\ldots,c_{i,n})=(c_{j,0},\ldots,c_{j,n}).$$ Moreover, the function $$\left\{\begin{array}{ccc} \{0,\ldots,n\} & \rightarrow & \{1,\ldots,n\} \\ k & \mapsto & c_{i,k} \end{array}\right.$$ has a domain of cardinal $$n+1$$ and an image of cardinal $$n$$. Note that the function $$k\mapsto c_{j,k}$$ is the same function. By the pigeonhole principle, there exist $$k\neq l\in\{0,\ldots,n\}$$ such that $$c_{i,k}=c_{j,k}=c_{i,l}=c_{j,l}.$$ This gives the desired rectangle.