Friday, October 21, 2016

mathematics - Keep the grid differences below $x$


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?



Answer



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.


No comments:

Post a Comment

classical mechanics - Moment of a force about a given axis (Torque) - Scalar or vectorial?

I am studying Statics and saw that: The moment of a force about a given axis (or Torque) is defined by the equation: $M_X = (\vec r \times \...