, 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 + \dots + a_k = d \cdot k$ and $0 \le d < k$. Then $a_1 + a_2 + \dots + 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 + \dots + 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 + \dots + 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 + \dots + 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 + \dots + a_k = d_k \cdot k$, $d_k \ge 0$, and by hypothesis $a_1 + a_2 + \dots + 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 + \dots + a_k \le a_1 + 1 + 2 + \dots + (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.