The minimum range of a $n \times n$ grid Let $n > 1$ be a integer, we put $1, 2, \cdots n^2$ into the cells of a $n \times n$ grid.
Let the range of the grid be the maximal difference between two cells that are in the same row or in the same column. Find the minimum range of all possible grids.
 A: For $n$ even let $n=2k$.
$\left(\begin{array}{cccccc}
1&\cdots & k^2-k + 1&k^2+1&\cdots&2k^2-k+1\\
\vdots  & \ & \vdots& \vdots&\ &\vdots\\
k &\cdots & k^2 & k^2+k& \cdots \ & 2k^2\\
n^2-2k^2+1&\cdots&n^2-k^2-k+1&n^2-k^2+1&\cdots&n^2-k+1\\
\vdots&\ &\vdots&\vdots&\ &\vdots\\
n^2-2k^2+k&\cdots&n^2-k^2&n^2-k^2+k&n^2-k&n^2\\
\end{array} \right)$
is an optimal solution. ($\cdots$) stands for "increasing by $k$" and ($\ \vdots\ $) for "increasing by $1$".
All rows and columns are increasing. We therefore find the range by considering the differences of the last and first entry in each row and column. The maximum for this is $n^2-2k^2+k-1$, or in terms of $n$: $$\frac{n^2}{2}+\frac n 2 -1.$$
Proof that this is optimal: We are trying to place the smallest and the largest numbers in a way in which they interfere (i.e. are in the same row or column) with the least difference. This is done by putting the smallest $k^2$ numbers in the top left corner and the largest $k^2$ in the bottom right. The next number we have to place is $k^2+1$ (or equivalently $n^2-k^2$). You will see that this yields that the minimum difference in the row or column in which we place it is $n^2-2k^2+k-1$. By filling up the other fields, we obtain an optimal matrix.
For odd $n$ the lowest $\left(\frac{n+1}2\right)^2$ numbers can be put in the top left corner and the highest $\left(\frac{n-1}2\right)^2$ in the bottom right. This would give a minimum range of $$n^2-\left(\frac{n-1}{2}\right)^2-\left(\frac{n+1}{2}\right)^2+\frac{n-1}{2}=\frac 1 2 (n^2+n-2),$$
as this is the minimal difference between the lest element which does not fit into the bottom right corner any more and the elements in the top left corner it interferes with.
A: Some thoughts on small cases:
$$n=1: (1) \text{ has range } 0 \text{ (trivial)} \\
n=2: \pmatrix{1&2\\3&4} \text{ has range } 2 \text{ (trivial)} \\
n=3: \pmatrix{1&2&5\\3&6&8\\4&7&9} \text{ has range } 5 \text{ (seems optimal)}$$
The general Idea:
WLOG Put a $1$ in the $A_{11}$ entry and $n^2$ in any entry not in $A_{1\cdot}$ not in $A_{\cdot1}$. Proceed alternating smallest / biggest placement and try to minimze the "partial range" i.e. the range disregarding empty entries.
