<s>[INST] Question about Permutations, and the distinct differences I have the following question regarding permutations of the sequence $(1,2,\cdots,n)$:
For what values of $n$ does there exist a permutation $(x_1,x_2,\cdots,x_n)$ of $(1,2,\cdots,n)$, such that the differences $|x_k-k|$ for each $k\in\{1,2,\cdots,n\}$ are all distinct?
I have shown that $n$ must not be congruent to 2 or 3 modulo 4. I have tried to construct a permutation for each value of $n$ congruent to 0 or 1 modulo 4, but I was not able to find a pattern, and as such I was unable to come up with a permutation for higher values of $n$.
Is there a nice way of actually constructing the desired permutations, or are there yet more values of $n$ for which such a permutation does not exist?
 [/INST] I'm not sure, but I think I've found a construction for $n=0\mod 4$. First, some examples:
$$\begin{pmatrix}1 & 4 & 2 & 3\\
4 & 2 & 1 & 3
\end{pmatrix} \\
\begin{pmatrix}1 & 8 & 2 & 7 & 3 & 5 & 4 & 6\\
8 & 2 & 7 & 3 & 5 & 4 & 1 & 6
\end{pmatrix} \\
\begin{pmatrix}1 & 12 & 2 & 11 & 3 & 10 & 4 & 8 & 5 & 7 & 6 & 9\\
12 & 2 & 11 & 3 & 10 & 4 & 8 & 5 & 7 & 6 & 1 & 9
\end{pmatrix} \\
\begin{pmatrix}1 & 16 & 2 & 15 & 3 & 14 & 4 & 13 & 5 & 11 & 6 & 10 & 7 & 9 & 8 & 12\\
16 & 2 & 15 & 3 & 14 & 4 & 13 & 5 & 11 & 6 & 10 & 7 & 9 & 8 & 1 & 12
\end{pmatrix}
$$
Generally, if $n=4k$, the permutation has a single cycle that is composed from alternating numbers from $1,2,\dots$ and $n,n-1,\dots$ but skips $3k$.
Also for $n=1\mod 4$ consider the examples:
$$
\begin{pmatrix}1 & 5 & 3 & 4 & 2\\
5 & 3 & 4 & 1 & 2
\end{pmatrix}
\\
\begin{pmatrix}1 & 9 & 2 & 8 & 4 & 7 & 5 & 6 & 3\\
9 & 2 & 8 & 4 & 7 & 5 & 6 & 1 & 3
\end{pmatrix}
\\
\begin{pmatrix}1 & 13 & 2 & 12 & 3 & 11 & 5 & 10 & 6 & 9 & 7 & 8 & 4\\
13 & 2 & 12 & 3 & 11 & 5 & 10 & 6 & 9 & 7 & 8 & 1 & 4
\end{pmatrix}
$$
Generally, if $n=4k+1$, the permutation has a single cycle that is composed from alternating numbers from $1,2,\dots$ and $n,n-1,\dots$ but skips $k+1$.
</s>