Permutations where the values $|\sigma(k)-k|$ are distinct

Question

Find the values of $n \geq 1$ for which there exists a permutation $\sigma$ of $\left\{1, \dots, n\right\}$ such that $|\sigma(k) - k|$ are distinct for each $k = \overline{1, n}$.

My idea is to prove that the structure is possible for $n := 4k$ and $n := 4k + 1$, while not being possible for $n := 4k + 2$ and $n := 4k + 3$. For showing the impossibility part, i have defined a parameter: $$T = \sum_{k = 1}^n |\sigma(k) - k|$$

Since $a \equiv |a| \ (\text{mod} \ 2)$, $T \equiv S \ (\text{mod} \ 2)$, where $S$ parameter is defined as: $$S = \sum_{k = 1}^n (\sigma(k) - k) = 0$$

So, the parameter $T$ is an even number.

However, since all the absolute values of the differences are distinct, they have all the values from $0$ to $n - 1$, so: $$T = \sum_{q = 0}^{n - 1} q = \frac{(n - 1)n}{2}$$

Which means that $n := 4k + 2$ and $n := 4k + 3$ are not viable solutions (easy to verify by plugging in the values and observing by calculation that $T$ is odd, which is obviously false.

However, I am not able to prove the example construction part. I have some examples for $n = 4 : [4 - 2 - 1 - 3]$ and for $n = 5 : [5 - 2 - 4 - 1 - 3]$, but I still can't generalize them.

Answer 1

You can find the solution in:

M. J. Pelling and J. H. Steelman, E3269. Permutations with distinct displacements, (problem by Pelling and solution by Steelman), The American Mathematical Monthly, 96 (1989), 843-844. I have found the reference at OEIS A042948.

The part that you are missing is:

Conversely, if $n \equiv 0$ or $1 \pmod 4$, one can construct a permutation with the desired property by letting

$$\sigma(k) = \begin{cases} n+1-k, & \text{if $1 \le k \le \lfloor n/4 \rfloor$} \\ n-k, & \text{if $\lfloor n/4 \rfloor \lt k \lt \lceil n/2 \rceil$} \\ 1, & \text{if $k = \lceil n/2 \rceil$} \\ n+1-k, & \text{if $\lceil n/2 \rceil \lt k \lt \lceil 3n/4 \rceil$} \\ k, & \text{if $k = \lceil 3n/4 \rceil$} \\ n+2-k, & \text{if $\lceil 3n/4 \rceil \lt k \le n$} \\ \end{cases}$$