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.

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$

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$.

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.

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

Is it ok now?

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

How much questions are u all expecting correct

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$