Permutation with distinct prefix sums

Source

Determine if there is a permutation $\sigma=(\sigma_0,\dots,\sigma_{n-1})$ of $\{0,1,\dots,n-1\}$ such that $s_0,s_2,\dots,s_{n-1}$ are all distinct where $$s_i:=\left(\sum_{j=0}^i\sigma_i\right)\mod n.$$

======================================================================

Solution

For such permutation to exist, we need $\sigma_0=0$. Otherwise $\sigma_i=0$ where $i\ne0$ implies that $s_{i-1}=s_i$.

For any odd $n$ such permutation does not exist, because $$\sigma_1+\sigma_2+\dots+\sigma_{n-1}=n(n-1)/2$$ is divisible by $n$, and $s_0=s_{n-1}$.

For an even $N$, let $$\sigma=(0, n-1, 2, n-3,4,\dots,n-4,3,n-2,1)$$ with $s_{n/2}=n/2$. It is interesting to see that the resulting prefix sums are $$s=(0,n-1,1,n-2,2,\dots,n/2+1,n/2-1,n).$$