In a sequence of $n$ integers, must there be a contiguous subsequence that sums to a multiple of $n$?

Question

Let $x_1, \ldots, x_n$ be integers. Then are there indices $1\le a\le b\le n$ such that $$\sum_{i=a}^b x_i$$ is a multiple of $n$?

Answer 1

Let $$s_k = \sum_{i=1}^k x_i\pmod n.$$ If $s_k$ is zero for any $k$, we have found the desired subsequence ($a=1, b=k$), so suppose all the $s_k$ are nonzero. There are $n$ of them, each in the range $1,\ldots,n-1$, so two, say $s_{a}$ and $s_b$, must be equal. Then since $s_b - s_a = 0$, we have $$\begin{align} \sum_{i=1}^b x_i - \sum_{i=1}^{a} x_i & = 0\pmod n \\ \sum_{i=a+1}^b x_i & = 0\pmod n \end{align}$$

as desired.

(Note that if $a+1 = b$, that is all right; it just means that $x_b$ itself is a multiple of $n$.)