For any sequence of $n$ integers, there exists a subsequence whose sum is divisible by $n$.

Question

So I'm confused and stuck on how to approach this question. Any direction in the right path would be greatly appreciated.

Let $n\in N$. Prove that any sequence of $n$ integers $a_1, a_2, \ldots,a_n$ (no restriction on whether they are positive or negative, repetition is also possible), there exists a non-empty subsequence of consecutive integers such that their sum is divisible by $n$. This subsequence could have any length from $1$ to $n$. In other words, there exists two integers $i, j$ where $1\le i\le j \le n$ such that $\sum\limits_{k=i}^j$$a_k$ is divisible by $n$.

For example, when $n=5$, the sequence $-12, 53, 3, 3, -44$ contains a subsequence $52, 3, 3, -44$ whose sum is $15$, which is divisible by $5$.

Hint. Consider the $n$ sums of $a_1, a_1 + a_2, a_1 + a_2 + a_3, \ldots, a_1 + a_2, + \cdots + a_n$.

If any of these sums is divisible by $n$, then we are done. What happens if none of them is divisible by $n$?

Answer 1

Consider the $n$ sums: $$s_k = \sum_{j=1}^k a_j$$

and their remainder after a division by $n$: $$n|s_k-r_k$$

There are $n$ of them. If one of them is 0: take $s_k$ and you are done.

Otherwise, there are $n-1$ possibilities for the possible values of $r_k$, so (pigeonhole principle) there are $p<q$ such as $r_p = r_q$, and so you take $\sum_{j=p+1}^q a_j$ and you are done.

Answer 2

Since we are interested in divisibility, we can consider the problem mod n. So our sequence $a_1,a_2,\ldots,a_n$ are all in $\{0,1,2,...,n-1\}$. Assume that there is no sequence of length 1 that adds to a multiple of $n$. Then use induction. Obviously for $n=1$ this is true. Try using induction.