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?

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

I think your answer is perfectly fine. It's rigorous and correct.

I do think we can simplify the proof, but it's essentially the same reasoning, so there's no need for you to change the proof, especially if it's one you came up with on your own :)

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.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.