4. Find all natural numbers $n$ for which there exists a permutation $\left(p_{1}, p_{2}, \ldots, p_{n}\right)$ of numbers $(1,2, \ldots, n)$ such that the sets $\left\{p_{i}+i \mid 1 \leq i \leq n\right\}$ and $\left\{p_{i}-i \mid 1 \leq i \leq n\right\}$ form complete sets of residues modulo $n$.

(Marko Djikić)
4. Suppose that such a permutation exists. Since $\left\{p_{i}+i \mid 1 \leq i \leq n\right\}$ is a complete residue system modulo $n$, we have $\sum_{k=1}^{n} k \equiv \sum_{i=1}^{n}\left(p_{i}+i\right) \equiv \sum_{i=1}^{n} i+\sum_{i=1}^{n} p_{i} \equiv$ $2 \sum_{k=1}^{n} k(\bmod n)$, hence $\sum_{k=1}^{n} k=\frac{n(n+1)}{2} \equiv 0(\bmod n)$, which gives us $2 \nmid n$. Moreover, it holds that $2 \sum_{k=1}^{n} k^{2} \equiv \sum_{k=1}^{n}\left(\left(p_{i}+i\right)^{2}+\left(p_{i}-i\right)^{2}\right) \equiv \sum_{k=1}^{n}\left(2 p_{i}^{2}+2 i^{2}\right) \equiv$ $4 \sum_{k=1}^{n} k^{2}$, so $2 \sum_{k=1}^{n} k^{2}=\frac{n(n+1)(2 n+1)}{3} \equiv 0(\bmod n)$, implying $3 \nmid n$. Therefore, we must have $(n, 6)=1$.

On the other hand, if $(n, 6)=1$ and $p_{i} \equiv 2 i(\bmod n), p_{i} \in\{1, \ldots, n\}$, then $\left(p_{1}, p_{2}, \ldots, p_{n}\right)$ is permutation of $\{1, \ldots, n\}$ and satisfies the conditions, because $\left\{p_{i}+i \mid 1 \leq i \leq n\right\} \equiv\{3 i \mid 1 \leq i \leq n\}$ and $\left\{p_{i}-i \mid 1 \leq i \leq n\right\} \equiv\{i \mid 1 \leq i \leq n\}$ $(\bmod n)$ are complete residue systems modulo $n$.