Consider \(n^2\) unit squares in the \(xy\) plane centered at point \((i,j)\) with integer coordinates, \(1 \leq i \leq n\), \(1 \leq j \leq n\). It is required to colour each unit square in such a way that whenever \(1 \leq i < j \leq n\) and \(1 \leq k < l \leq n\), the three squares with centres at \((i,k),(j,k),(j,l)\) have distinct colours. What is the least possible number of colours needed?
Problem
Source: RMO 2017 P4
Tags: combinatorics, pigeonhole principle
08.10.2017 14:21
The answer is $2n-1$. Clearly it holds for $n=1$, so let $n>1$ for now. Consider the squares in the rightmost column and the bottommost row; we claim that these $2n-1$ squares all have different colours. Indeed, suppose not. Then some two of these squares have the same colour. If they both belong to the rightmost column, say $(a,n) , (b,n)$, with $b>a$, then considering squares $(a,n) , (b,n) , (b,1)$ gives us a contradiction. Similarly, the two squares of the same colour cannot both be in the bottommost row. Otherwise one of them belongs to the rightmost column, say $(a,n)$, and the other belongs to the bottommost row , say $(n,b)$ and they are both different from $(n,n)$. Considering the two squares and the square $(n,n)$ gives us a contradiction. To prove that a construction with $2n-1$ colours exist, colour all squares $(i,j)$ the same value of $i+j$ with the same colour.
08.10.2017 14:47
For $k \in [2, \cdots , 2n]$, color all tuples $(x,y)$ satisfying $$x+y=k$$same color to get a different construction of the bound $2n-1$
08.10.2017 15:41
I did it using recursion. If $a_n$ is the minimum number of colourings for $n\times n$ square, then we add one more row to its up and one more column to its left. The left-most row can be coloured the same. Same for the up-most column. So, this column must have different colours from that included in $a_n$. So $+1$. This new row also must have another colour, which is different from the column-colour. So, another $+1$. So, $a_{n+1}=a_n+2$. This is an AP which gives, $a_n=2n-1$.
08.10.2017 18:37
polarLines wrote: I did it using recursion. If $a_n$ is the minimum number of colourings for $n\times n$ square, then we add one more row to its up and one more column to its left. The left-most row can be coloured the $\color{red}{same.}$ Same for the up-most column. So, this column must have different colours from that included in $a_n$. So $+1$. This new row also must have another colour, which is different from the column-colour. So, another $+1$. So, $a_{n+1}=a_n+2$. This is an AP which gives, $a_n=2n-1$. The condition simply says that take any row or column, it's squares must have distinct colours. So your configuration is surely wrong.
08.10.2017 19:18
Ghoshadi wrote: polarLines wrote: I did it using recursion. If $a_n$ is the minimum number of colourings for $n\times n$ square, then we add one more row to its up and one more column to its left. The left-most row can be coloured the $\color{red}{same.}$ Same for the up-most column. So, this column must have different colours from that included in $a_n$. So $+1$. This new row also must have another colour, which is different from the column-colour. So, another $+1$. So, $a_{n+1}=a_n+2$. This is an AP which gives, $a_n=2n-1$. The condition simply says that take any row or column, it's squares must have distinct colours. So your configuration is surely wrong. Sorry...it will be leftmost-column and upmost row....how can there be a leftmost row and an upmost column
08.10.2017 19:25
Is it ok now?
08.10.2017 20:03
Ghoshadi wrote: polarLines wrote: I did it using recursion. If $a_n$ is the minimum number of colourings for $n\times n$ square, then we add one more row to its up and one more column to its left. The left-most row can be coloured the $\color{red}{same.}$ Same for the up-most column. So, this column must have different colours from that included in $a_n$. So $+1$. This new row also must have another colour, which is different from the column-colour. So, another $+1$. So, $a_{n+1}=a_n+2$. This is an AP which gives, $a_n=2n-1$. The condition simply says that take any row or column, it's squares must have distinct colours. So your configuration is surely wrong. Why it's wrong with a left most column and uppermost row we have covered all l configurations and left with only the new ones in those n+(n-1) cells
08.10.2017 20:52
How much questions are u all expecting correct
01.03.2022 08:59
Solution: Notice that the points $(i,k), (j,k), (j,l)$ are always the vertices of a Right Triangle. Hence, it is easy to see that the half the boundary squares(i.e. the $2n-1$ squares) must all be of different colours. Otherwise a contradiction would arise. And construction for $2n-1$, just colour all diagonals with assigned colours in the $2n-1$ squares and we're done.$\blacksquare$