Determine all natural numbers $n$ for which there exists a permutation $(a_1,a_2,\ldots,a_n)$ of the numbers $0,1,\ldots,n-1$ such that, if $b_i$ is the remainder of $a_1+a_2+\cdots+ a_i$ upon division by $n$ for $i=1,\ldots,n$, then $(b_1,b_2,\ldots,b_n)$ is also a permutation of $0,1,\ldots,n-1$.
My progress:
So $b_i\equiv a_1+\dots + a_i\mod n.$
So $$\sum_{i=1}^n b_i=a_1+a_1+a_2+a_1+\dots+\dots +a_1+\dots +a_n\equiv n\cdot a_1+(n-1)\cdot a_2 +\dots +2\cdot a_{n-1}+a_n \mod n$$
Let's take examples
- For $n=2,$
we get $(0,1)\rightarrow (0,1)$ works.
- For $n=3,$
it's not possible.
Now, looking at $n=3$ case, we have a claim.
Claim: If $a_i\ne 0,~~1<i$
Proof: If not then $b_{i-1}=b_i.$
So we want each $b_i$ to be distinct. Hence for any $k$ -consecutive $a_i,$ we have $$a_{i}+\dots+a_{i+k-1}\not\equiv 0\mod n$$
Now, clearly $n$ is even. Since, if not, then $n|\frac{n(n-1)}{2}.$
So we will have $b_1=b_n.$
Let take some more examples,
- For $n=4,$
We get that $(0,1,2,3)\rightarrow (0,1,3,2).$
- For $n=6,$
We get that $(0,2,5,3,1,4)\rightarrow (0,2,1,4,5,3).$
I think it is true for all evens..
Best Answer
Good observation. So now that $n$ is even, can you produce the permutation $(0,n-1,1,n-2,2,n-3,3,\cdots)$?
Hint: Think in pairs and notice that $\ell \cdot (n-1)\equiv n-\ell \pmod n$