Can you rearrange natural numbers so sum of first $n$ is divisible by $n$ for every $n$?

Question

Can you rearrange natural numbers so sum of first $n$ is divisible by $n$ for every $n$?

I want to prove this by induction, if we rearrange first $n$ numbers we can always choose an integer so sum is divisible by $n+1$. But how can I prove every number will be used?

Example: $1, 3, 2, 6, 8$ and so on...

Thanks in advance

Answer 1

Here is my proof:

Let $a_1 = 1$, that is base of induction.

Inductive hypothesis: We have valid array $a_1, a_2,...,a_n$. Now let $x$ be the smallest number which is not in array yet. Let $a_{n+2} = x$, by chines reminder theorem, we know there exist $a_{n+1}$ so $n+1|\sum_{i=1}^{n+1}a_i$ and $n+2|\sum_{i=1}^{n+2}a_i$. Now we have valid array with length $n+2$ and we can guarantee all natural numbers will be in array, for some large enough $n$.

Answer 2

The greedy algorithm (select the smallest distinct number that works) does work, and you will get OEIS A019444. One of the references there – Venkatachala (2009) – proves that it is an involution (stronger than permutation) of the natural numbers.