, 2015

Let $r_k$ be the remainder of the partial sum $a_1 + a_2 + \dots + a_k$ upon division by $n$, and let $m$ be the number of distinct residues in the list $r_1, r_2, \dots, r_n$. Since there are $m$ distinct integers in the list, the number of ordered pairs with different entries that can be formed from these $m$ integers does not exceed $m(m-1)$. On the other hand, of the $n-1$ distinct ordered pairs $(r_k, r_{k+1})$, $k = 1, 2, \dots, n-1$, at most one has equal entries, so $m(m-1) \ge (n-1)-1 = n-2$. Consequently, $m \ge (1+\sqrt{4n-7})/2 \ge \sqrt{n}$ if $n \ge 4$, the latter inequality being strict if $n \ge 5$. If $n=4$, and $a_1=2$, $a_2=4$, $a_3=3$ and $a_4=1$, then the corresponding list of residues is 2, 2, 1, 2, so $m=2 = \sqrt{4} = \sqrt{n}$. Finally, if $n=3$, then every permutation produces a list consisting of exactly $2 > \sqrt{3}$ distinct residues. (If $n=2$, the identity produces the list 1, 1, so $m=1 < \sqrt{2} = \sqrt{n}$.)