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$?
Best Answer
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.