Slovenija 2008

Taking a look at the sequences we obtain for different values of $a_1$, we notice the following: Assume there is an index $k$ such that $a_1+a_2+\cdots +a_k=d\cdot k$ and $0\le d<k$. Then $a_1+a_2+\cdots +a_k+d=d\cdot (k+1)$ and since $a_{k+1}$ is a uniquely determined number between $0$ and $k$ such that $a_1+a_2+\cdots +a_{k+1}$ is divisible by $k+1$, we have $a_{k+1}=d$. We come to the same conclusion about all subsequent terms of the sequence, so this sequence is constant and equal to $d$ from $a_{k+1}$ onward.

Let us show that for all choices of $a_1$ there exists an index $k$ such that $a_1+a_2+\cdots +a_k=d\cdot k$ and $0\le d<k$. Assume, to the contrary, that this is not the case. If $a_1<0$ and the sequence is not constantly $0$ from some point onward, there are infinitely many positive terms, so there exists an index $k$ such that $a_1+a_2+\cdots +a_k\ge 0$. If by chance we have $a_1>0$, then this is true for all $k$. So, for $k$ sufficiently large we have $a_1+a_2+\cdots +a_k=d_k\cdot k$, $d_k\ge 0$, and by hypothesis $a_1+a_2+\cdots +a_k\ge k^2$. We can bound the terms by $a_2\le 1$, $a_3\le 2$ and $a_i\le i-1$ for all $i>1$. So (for $k$ sufficiently large) we have $$k^2\le a_1+a_2+\cdots +a_k\le a_1+1+2+\cdots +(k-1)=a_1+\frac{k(k-1)}{2},$$ which means that for all $k$ from some point onward we have $$a_1\ge \frac{k(k+1)}{2}.$$ Evidently, this last inequality is not always satisfied, for example when $k\ge 2|a_1|$. We have arrived at a contradiction which implies that the initial assumption was incorrect.

Hence, we have shown there exists an index $k+1$ such that from $k+1$ onward all terms of the sequence are equal.