5
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ The worst case is 4 since this is just a special case of the map coloring problem $\endgroup$ – Dr Xorile Jan 7 at 15:10
  • $\begingroup$ @DrXorile I disagree. I think the graph corresponding to this problem is not planar when $N,M$ are large enough ($N=M=4$?), which is one of the prerequisites for the four-colour theorem to apply. The worst case may be $4$ nevertheless, but not because of that. $\endgroup$ – Jaap Scherphuis Jan 7 at 16:15
  • 1
    $\begingroup$ @Jaap, I cannot see how a 2d matrix could be anything but planar $\endgroup$ – Dr Xorile Jan 7 at 16:44
  • 1
    $\begingroup$ @DrXorile I'm with Jaap on this, I don't see the connection. For instance, you can change the problem from "square" cells to hexagonal ones where each hexagon has to border six, each containing different numbers. How would the analogue generalise? $\endgroup$ – hexomino Jan 7 at 17:47
  • 1
    $\begingroup$ @Hugh, no problem at all! I see from your history you like to make grammar edits whenever possible, which is great, so just wanted to make sure. Keep it up! $\endgroup$ – tilper Jan 8 at 12:28
3
$\begingroup$

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 enter image description here
(ii) Proceed analogously for the white squares in the even-numbered columns and the numbers $3$ and $4$, as shown enter image description here
(iii) Now do exactly the same for the black squares and we are done enter image description here
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) $$

$\endgroup$
2
$\begingroup$

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

enter image description here

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.

$\endgroup$
  • $\begingroup$ This is incorrect. A cell cannot have neighbors that are identical to itself. $\endgroup$ – Hugh Jan 7 at 15:07
  • $\begingroup$ I don’t think that is specified in the question and the example has a cell with a neighbour which is identical. $\endgroup$ – Magic turtle Jan 7 at 15:08
  • $\begingroup$ The example may be wrong. The question says, under rule 2: for any cell C, all its' adjacent neighbors [i.e. bottom, top, left, right cells] must have different values $\endgroup$ – Hugh Jan 7 at 15:12
  • $\begingroup$ I think the wording is ambiguous but the example would suggest that the cell itself is not included in its adjacent cells $\endgroup$ – Magic turtle Jan 7 at 15:20
  • $\begingroup$ Edit oh, sorry. I've been reading it wrong. Please ignore that. $\endgroup$ – Hugh Jan 7 at 15:22
1
$\begingroup$

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

$\endgroup$

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.