a_507_bc wrote: Let $n$ be a positive integer. Each cell of an $n \times n$ table is coloured in one of $k$ colours where every colour is used at least once. Two different colours $A$ and $B$ are said to touch each other, if there exists a cell coloured in $A$ sharing a side with a cell coloured in $B$. The table is coloured in such a way that each colour touches at most $2$ other colours. What is the maximal value of $k$ in terms of $n$? By a path in the table $T$ we mean a path from one cell to an other using cells sharing a side with each other. Assume that the cells in the table are $\{0,1,\ldots,n-1\}\times\{0,1,\ldots,n-1\}$ Consider a graph $G$ with the $k$ colour as vertices such that there is an edge between two colours if, and only if they touch each other. $G$ is connected since for every two colours $A,B$ there is a path in $T$ from a cell with colour $A$ to a cell with colour $B$ giving us a path from $A$ to $B$ in $G$. Since every vertex in $G$ has degree $\leq2$ the graph $G$ is either a circle of length $k$ or a line with $k$ vertices. For odd $n$ every cell in $T$ can be reached from $\left(\frac{n-1}{2},\frac{n-1}{2}\right)$ in at most $n-1$ steps. So $G$ can have at most $2n-1$ vertices and we have $k\leq2n-1$. For even $n$ every cell in $T$ can be reached from $\left(\frac{n}{2},\frac{n}{2}\right)$ in at most $n$ steps. $(0,0)$ is the unique vertex that can be reached in at most $n$ steps. So $G$ can have at most $2n$ vertices and we have $k\leq2n$. However for $n\geq4$ the $5$ that can not be reached in $2n-2$ steps from $\left(\frac{n}{2},\frac{n}{2}\right)$ are $(0,0),(1,0),(0,1),(n,0),(0,n)$. If $(0,0)$ has a colour $C$ with distance $n$ in $G$ from the colour $D$ of $\left(\frac{n}{2},\frac{n}{2}\right)$ it is the only cell with colour $C$. If $(1,0),(0,1)$ have different colours, $G$ must be a circle of length $2n$. So $(1,1)$ must be coloured with $C$ contradicting the uniqueness. If $(1,0),(0,1)$ have the same colour, the colours of $(n,0),(0,n)$ are reachable from $(1,0),(0,1)$ respectivly in $n-1$ steps in $G$ with a path not containing $C$. In particular they can not be a second colour with distance $n-1$ from $D$. Thus $k\leq 2n-1$ for even $n\geq4$. These bonds can be achieved by giving $(i,j)$ the colour $i+j$ for $n\neq2$. For $n=2$ colour each cell with a unique colour.

Cute induction one. Posting this because the above solution is too brilliant for me. We induct on $n$, base case $n=1$ is trivial. Follow this solution with a drawing for a better understanding. Also, the claim is that the answer is $2n-1$, achieved by colouring diagonally. Suppose this is the answer for $n$ and let $T$ be the $n+1$x$n+1$ board. Suppose we have coloured $T$ with $\geq 2n+2$ colours. Then, as the left-top $n$x$n$ board inside $T$ also satisfies that every colour has at most 2 neighbors. Then, there must be at most $2n-1$ colours inside it, by induction hypothesis. Thus, there are at least three other colors that haven't appeared before that are now on the last line or last column. Call them $X,Y,Z$. As there are three, suppose $X$ is not the right-bottom one. Thus it has a neighbor (call it $P$) on the $n$x$n$ used on the induction hypothesis (call this other board $T'$). Then, as $X$ can't be used on $T'$, $P$ has all its neighbors of the same colour (call it $A$). Define, finally, $B$ as the common neighbor of $A,X$. All of that is for the reader to notice the whole "$T-T'$ column/line" part of the board is well defined, and it can only contain $A,X,P,U$ as colours. Notice $A,P$ were used on $T'$, so they can't be the new colours. We only remain with $U,X$ to be the new ones, but this is a contradiction since we supposed there were 3 new colours. This completes the induction, done =0

Gaty gowy

For n=2 the answer can be 4?