Determine all integers $n\geq 1$ for which the numbers $1,2,\ldots,n$ may be (re)ordered as $a_1,a_2,\ldots,a_n$ in such a way that the average $\dfrac {a_1+a_2+\cdots + a_k} {k}$ is an integer for all values $1\leq k\leq n$. (Dan Schwarz)
Problem
Source: Stars Of Mathematics 2014, Juniors, Problem 2
Tags: number theory, combinatorics
09.03.2015 16:17
We have $\frac{a_1+a_2+...+a_n}{n}=\frac{1+2+...+n}{n}=\frac{n+1}{2}\in\mathbb{N}$,so $n\equiv 1(mod 2)$.$n=1$ is obviously a solution,so from now on let's suppose that $n\ge 3$.We also have $\frac{a_1+a_2+...+a_{n-1}}{n-1}=\frac{\frac{n(n+1)}{2}-a_{n}}{n-1}\in\mathbb{N}$.Let $\frac{n(n+1)}{2}-a_{n}=(n-1)k,k\in\mathbb{N}$ and $n=2l+1,l\in\mathbb{N}$.Therefore $2l^2+l+1-a_{n}=2lk$,which implies $a_{n}\equiv 1(mod l)$ i.e. $a_n\equiv 1(mod \frac{n-1}{2})$.From here we obtain $a_n\in\{1,\frac{n+1}{2},n\}$. If $a_n=1$,then $2l^2+l=2lk$,which is equivalent to $2l+1=2k$,contradiction!If $a_{n}=n=2l+1$,then $2l^2+l+1-(2l+1)=2l^2-l=2kl$,which is equivalent to $2l-1=2k$,contradiction!Thus $a_{n}=\frac{n+1}{2}$. Now suppose that $n\ge 5$.We have $\frac{a_1+a_2+...+a_{n-2}}{n-2}=\frac{\frac{n(n+1)}{2}-a_n-a_{n-1}}{n-2}=\frac{\frac{n(n+1)}{2}-\frac{n+1}{2}-a_{n-2}}{n-2}=\frac{\frac{n+1}{2}(n-1)-a_{n-1}}{n-2}\in\mathbb{N}$,from which it follows that $(n-1)\frac{n+1}{2}\equiv a_{n-1}(mod n-2)$,which is the same thing as $\frac{n+1}{2}\equiv a_{n-1}(mod n-2)$.Since $n\ge 5$ we have $\frac{n+1}{2}\le n-2$ and $\frac{n+1}{2}+(n-2)>2+(n-2)=n$,forcing $a_{n-1}=\frac{n+1}{2}=a_{n}$,contradiction! Therefore $n\ge 3$.For $n=3$ we can take $a_1=1,a_2=3$ and $a_3=2$. In conclusion,the only solutions are $n\in\{1,3\}$.
28.03.2015 22:43
This problem has also a general case: Does there exist an infinite sequence which contains every natural number exactly once and such that $ x_1+x_2+...+x_k $ is divisible by every integer $ k $? Proof: The answer is yes. Let $ x_1=1 $. Suppose that $ x_1$ ,...$ x_n$ have been chosen and their sum is $S$. We can construct another element as follows: Let $ s $ an integer not yet chosen into the sequence and we give this value to $ x_{n+1} $. So for $ x_n$ we have the conditions: $ S+x_n \equiv 0 (mod n) $ and $ S+s+x_n \equiv 0 (mod n+1) $. $ x_n $ can be chosen by the Chinese Remainder Theorem. We can add a sufficiently large multiple of $ n(n+1) $ to obtain $ x_n $ bigger than the other elements. All the elements may eventually appear.