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

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}^ja_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$$?

• What would happen if you tried to use induction? Mar 5, 2014 at 3:36

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.

• The word you want is "remainder", not "rest". (Though the Spanish word is "resto".)
– Pedro
Mar 5, 2014 at 4:01
• Can you clarify what you mean by "if one of them is 0, then take $s_k$ and you are done" ? Do you mean that their is no remainder to consider? Mar 5, 2014 at 4:05
• @user3358732: is for example $r_2=0$, then $a_1 + a_2$ is a multiple of $n$. Mar 5, 2014 at 4:06

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.