3
$\begingroup$

Inspired by Keep the chessboard differences below eight

Given an $n\times m$ grid of squares, what is the smallest possible integer bound $x$ for which it is possible to fill the squares with the integers $1,\ldots,nm$ so that each two squares with a common edge have an absolute difference of $x$ or less? And what is the best strategy of finding such a grid?

$\endgroup$
5
$\begingroup$

You can do it with $x=\min(n,m)$. Put $1$ in the upper left and fill each diagonal starting at the bottom and going up and right in order. A $4 \times 5$ example is below:

$$\begin{array}{|r|r|r|r|r|}\hline \phantom{00}1 & \phantom{00}3 & \phantom{00}6 & \phantom010 & \phantom014\\\hline 2 & 5 & 9 & 13 & 17\\\hline 4 & 8 & 12 & 16 & 19\\\hline 7 & 11 & 15 & 18 & 20\\\hline \end{array}$$

To see this is the best possible, it is easier to do the $x \times x$ square as you (may) get to use smaller numbers for this part of the grid. Now follow the proof in the linked question to see that $x-1$ is not possible.

$\endgroup$
1
  • $\begingroup$ Excellent job! ${}$ $\endgroup$
    – warspyking
    Oct 10 '15 at 4:28

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .