Fill $N$ by $M$ grid with numbers in such a way that any given cells' neighbors are different

Question

Create an $N$ by $M$ grid with numbers in such a way that satisfies following conditions:

1. numbers should be integers that range from $1$ to $r$.
2. for any cell $C$, all its adjacent neighbors (i.e. bottom, top, left, right cells) must have different values.
3. $r$ must be minimal.

For example, a solution for a $3$ by $3$ grid is...

$\begin{bmatrix}1 & 2 & 2\\1 & 3 & 4\\2 & 3 & 1\end{bmatrix}$

In this case, $r = 4$.

Answer 1

I propose that

1. If $\min(N,M) \geq 3$ then $r=4$
2. If $\min(N,M) = 2$ and $\max(N,M) > 2$ then $r=3$
3. If $M=N=2$ then $r=2$
4. If $\min(N,M) = 1$ and $\max(N,M) > 2$ then $r=2$
5. If $\min(N,M) = 1$ and $\max(N,M) \leq 2$ then $r=1$

Proof
1.

If $\min(N,M) \geq 3$ then there is at least one cell surrounded by $4$ others and all have different values. Hence, $r \geq 4$.

Now suppose we colour the cells of the grid like a chessboard and do the following:
(i) In every odd-numbered column number the white squares $1$ and $2$ alternately, always beginning each column with the opposite number of the previous, as shown
(ii) Proceed analogously for the white squares in the even-numbered columns and the numbers $3$ and $4$, as shown
(iii) Now do exactly the same for the black squares and we are done
Hence we can always achieve $r \leq 4$ and in this scenario we have $r=4$

2.

If $\min(N,M) = 2$ but $\max(N,M) >2$, then we know there is at least one cell with $3$ neighbours. Hence, $r \geq 3$.

Without loss of generality suppose $N=2$ (i.e, $2$ rows but more than $2$ columns) then we can fill each row with the repeating sequence $1,2,3,1,2,3,\ldots$. That is, we have $$\left(\begin{array}{l}1&2&3&1&2&3&\ldots\\1&2&3&1&2&3&\ldots\end{array}\right) $$ That is, we have $r \leq 3$.

Hence, $r=3$ in this case.

3.

If $N=M=2$ then we know that $r \geq 2$ since each cell has $2$ neighbours.

To achieve $r=2$, we can put $1$s in the first column and $2$s in the second as shown $$\left(\begin{array}{l}1&2\\1&2\end{array}\right) $$

4.

If $\min(N,M) =1$ and $\max(N,M) > 2$ then there is at least one cell with $2$ neighbours so $r \geq 2$.

To achieve $r=2$, we can fill the single row (or column) with a repeating sequence $$ \left( 1,1,2,2,1,1,2,2,\ldots \right) $$

5.

There are just two cases here, really, and, in both, we can fill the grid with $1$s that is, $$ (1) \,\,\,\,\text{ and } \,\,\,\,(1 1) $$

Answer 2

The answer is always r = 4 in cases where m and n are greater than 2.



This pattern can be repeated across the grid and cut off at the edges. In the cases where m and n are greater than 2, there will be a 3x3 grid where, you have already said r = 4. When one of m or n is 2 and the other is greater, r = 3 because you can repeat [1,1] [2,2] and [3,3] but you need 3 because there will be a square with 3 around it. The pattern for a 1xm grid is 1,1,2,2,1,1 etc. In a 2x2 however the answer is r = 2 and in a 1x1 or 1x2 the answers are r = 1. These are fairly easy to see/test.

Answer 3

If all cells including itself must be different:

r=5, as this pattern tessellates:

 A B C D E
 D E A B C
 B C D E A
 E A B C D
 C D E A B