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$
  • $\begingroup$ Excellent job! ${}$ $\endgroup$ – warspyking Oct 10 '15 at 4:28

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.