Return to Question

This question is inspired by Martin Erickson's question, "Labeling a Square Array." I'll start by quoting Martin:

the $n^2$ cells of an $n \times n$ array are labeled with the integers $1, \dots, n^2$. Under the traditional left-to-right and top-to-bottom labeling, the labels of horizontally adjacent cells differ by $1$, and the labels of vertically adjacent cells differ by $n$.

Let $\delta$ be the minimum absolute label difference between any cells adjacent horizontally or vertically in a particular filling of the array by those $n^2$ numbers. So $\delta=1$ in the standard filling. What is the maximum of $\delta$ as a function of $n$?

In a sense, this is asking for a maximal "disarrangement" of the $n^2$ numbers. Phrased that way, it sounds like it may have applications and therefore be well-studied: perhaps in the discrepancy theory literature? Or perhaps it is entirely elementary...

Examples. For $n=2$, $\delta=1$, e.g., $$ \left( \begin{array}{cc} 3&2\\ 1&4 \\ \end{array} \right) \;. $$ For $n=3$, $\delta=3$, e.g., $$ \left( \begin{array}{ccc} 1&4&7\\ 5&8&2 \\ 9&3&6 \end{array} \right) \;. $$

Addendum. Here is an illustration of Gjergji Zaimi's solution, achieving, for $n=5$, $\delta=10=\binom{5}{2}$:
         Derrangement http://cs.smith.edu/~orourke/MathOverflow/SquareDerrangement.jpg

This question is inspired by Martin Erickson's question, "Labeling a Square Array." I'll start by quoting Martin:

the $n^2$ cells of an $n \times n$ array are labeled with the integers $1, \dots, n^2$. Under the traditional left-to-right and top-to-bottom labeling, the labels of horizontally adjacent cells differ by $1$, and the labels of vertically adjacent cells differ by $n$.

Let $\delta$ be the minimum absolute label difference between any cells adjacent horizontally or vertically in a particular filling of the array by those $n^2$ numbers. So $\delta=1$ in the standard filling. What is the maximum of $\delta$ as a function of $n$?

In a sense, this is asking for a maximal "disarrangement" of the $n^2$ numbers. Phrased that way, it sounds like it may have applications and therefore be well-studied: perhaps in the discrepancy theory literature? Or perhaps it is entirely elementary...

Examples. For $n=2$, $\delta=1$, e.g., $$ \left( \begin{array}{cc} 3&2\\ 1&4 \\ \end{array} \right) \;. $$ For $n=3$, $\delta=3$, e.g., $$ \left( \begin{array}{ccc} 1&4&7\\ 5&8&2 \\ 9&3&6 \end{array} \right) \;. $$

Addendum. Here is an illustration of Gjergji Zaimi's solution, achieving, for $n=5$, $\delta=10=\binom{5}{2}$:

This question is inspired by Martin Erickson's question, "Labeling a Square Array." I'll start by quoting Martin:

the $n^2$ cells of an $n \times n$ array are labeled with the integers $1, \dots, n^2$. Under the traditional left-to-right and top-to-bottom labeling, the labels of horizontally adjacent cells differ by $1$, and the labels of vertically adjacent cells differ by $n$.

Let $\delta$ be the minimum absolute label difference between any cells adjacent horizontally or vertically in a particular filling of the array by those $n^2$ numbers. So $\delta=1$ in the standard filling. What is the maximum of $\delta$ as a function of $n$?

In a sense, this is asking for a maximal "disarrangement" of the $n^2$ numbers. Phrased that way, it sounds like it may have applications and therefore be well-studied: perhaps in the discrepancy theory literature? Or perhaps it is entirely elementary...

Examples. For $n=2$, $\delta=1$, e.g., $$ \left( \begin{array}{cc} 3&2\\ 1&4 \\ \end{array} \right) \;. $$ For $n=3$, $\delta=3$, e.g., $$ \left( \begin{array}{ccc} 1&4&7\\ 5&8&2 \\ 9&3&6 \end{array} \right) \;. $$

Addendum. Here is an illustration of Gjergji Zaimi's solution, achieving, for $n=5$, $\delta=10=\binom{5}{2}$:
         Derrangement http://cs.smith.edu/~orourke/MathOverflow/SquareDerrangement.jpg

This question is inspired by Martin Erickson's question, "Labeling a Square Array." I'll start by quoting Martin:

the $n^2$ cells of an $n \times n$ array are labeled with the integers $1, \dots, n^2$. Under the traditional left-to-right and top-to-bottom labeling, the labels of horizontally adjacent cells differ by $1$, and the labels of vertically adjacent cells differ by $n$.

Let $\delta$ be the minimum absolute label difference between any cells adjacent horizontally or vertically in a particular filling of the array by those $n^2$ numbers. So $\delta=1$ in the standard filling. What is the maximum of $\delta$ as a function of $n$?

In a sense, this is asking for a maximal "disarrangement" of the $n^2$ numbers. Phrased that way, it sounds like it may have applications and therefore be well-studied: perhaps in the discrepancy theory literature? Or perhaps it is entirely elementary...

Examples. For $n=2$, $\delta=1$, e.g., $$ \left( \begin{array}{cc} 3&2\\ 1&4 \\ \end{array} \right) \;. $$ For $n=3$, $\delta=3$, e.g., $$ \left( \begin{array}{ccc} 1&4&7\\ 5&8&2 \\ 9&3&6 \end{array} \right) \;. $$

Addendum. Here is an illustration of Gjergji Zaimi's solution, achieving, for $n=5$, $\delta=10=\binom{5}{2}$:
         Derrangement http://cs.smith.edu/~orourke/MathOverflow/SquareDerrangement.jpg

This question is inspired by Martin Erickson's question, "Labeling a Square Array." I'll start by quoting Martin:

the $n^2$ cells of an $n \times n$ array are labeled with the integers $1, \dots, n^2$. Under the traditional left-to-right and top-to-bottom labeling, the labels of horizontally adjacent cells differ by $1$, and the labels of vertically adjacent cells differ by $n$.

Let $\delta$ be the minimum absolute label difference between any cells adjacent horizontally or vertically in a particular filling of the array by those $n^2$ numbers. So $\delta=1$ in the standard filling. What is the maximum of $\delta$ as a function of $n$?

In a sense, this is asking for a maximal "disarrangement" of the $n^2$ numbers. Phrased that way, it sounds like it may have applications and therefore be well-studied: perhaps in the discrepancy theory literature? Or perhaps it is entirely elementary...

Examples. For $n=2$, $\delta=1$, e.g., $$ \left( \begin{array}{cc} 3&2\\ 1&4 \\ \end{array} \right) \;. $$ For $n=3$, $\delta=3$, e.g., $$ \left( \begin{array}{ccc} 1&4&7\\ 5&8&2 \\ 9&3&6 \end{array} \right) \;. $$

This question is inspired by Martin Erickson's question, "Labeling a Square Array." I'll start by quoting Martin:

the $n^2$ cells of an $n \times n$ array are labeled with the integers $1, \dots, n^2$. Under the traditional left-to-right and top-to-bottom labeling, the labels of horizontally adjacent cells differ by $1$, and the labels of vertically adjacent cells differ by $n$.

Let $\delta$ be the minimum absolute label difference between any cells adjacent horizontally or vertically in a particular filling of the array by those $n^2$ numbers. So $\delta=1$ in the standard filling. What is the maximum of $\delta$ as a function of $n$?

In a sense, this is asking for a maximal "disarrangement" of the $n^2$ numbers. Phrased that way, it sounds like it may have applications and therefore be well-studied: perhaps in the discrepancy theory literature? Or perhaps it is entirely elementary...

Examples. For $n=2$, $\delta=1$, e.g., $$ \left( \begin{array}{cc} 3&2\\ 1&4 \\ \end{array} \right) \;. $$ For $n=3$, $\delta=3$, e.g., $$ \left( \begin{array}{ccc} 1&4&7\\ 5&8&2 \\ 9&3&6 \end{array} \right) \;. $$

Addendum. Here is an illustration of Gjergji Zaimi's solution, achieving, for $n=5$, $\delta=10=\binom{5}{2}$:
         Derrangement http://cs.smith.edu/~orourke/MathOverflow/SquareDerrangement.jpg