2015 Ninth STARS OF MATHEMATICS Competition

Let $r_k$ be the remainder of the partial sum $a_1+a_2+\cdots +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}$.)