Sum of freely chosen subset of $n$-tuple is divisible by $n$.

Question

I am struggling with the following task:

Be $n \in N$ and $(a_1, a_2, \ldots, a_n) \in \mathbb{Z}^n$. Prove that there is always $i, j \in \underline{n}$, with $i≤j$, so that $\sum_{k=i}^j a_k$ is divisible by n.

My first idea was to use a distinction of cases. In the first case a multiple of n is an element of $\mathbb{Z}^n$ so you could select the sum to be just this element so it would obviously be divisible.

In the second case, all elements of the tuple are the same, so that adding them all up will result in a multiple of $n$ once more, making it divisible.

I am lost however on what to do in the third case, where the two above are not true. I would truly appreciate your input.

Answer 1

Some elements of $(a_1, a_2, \ldots, a_n)$ may be different and it need not contain a multiple of $n$ of course. (it is chosen just randomly from $\mathbb{Z}^n$.)

You need a little trick to solve this problem in an easy way. Consider $n$ values $$ a_1, a_1+a_2, a_1+a_2+a_3, \ldots , a_1+a_2 +\cdots a_n. $$ If at least one of them is a multiple of $n$, it's okay. If not, what can be said about their remainders divided by $n$?

Answer 2

Using pigeonhole principle, let's look at all the remainders of $$a_1 \pmod{n}$$ $$a_1+a_2\pmod{n}$$ $$a_1+a_2+a_3\pmod{n}$$ $$...$$ $$a_1+a_2+a_3+...+a_n\pmod{n}$$ If at least one is $0$, we are done.

If none is $0$, then at least $2$ will have the same value (there will be $n$ remainders, taking $n-1$ possible values within $\{1,...,n-1\}$, pigeonhole principle). E.g. $$a_1+a_2+a_3+...+a_j \equiv a_1+a_2+a_3+...+a_i \pmod{n}$$ The remaining part is to subtract, assume $i<j$

$$(a_1+a_2+a_3+...+a_j)- (a_1+a_2+a_3+...+a_i)\equiv 0 \pmod{n}$$ or $$a_{j+1}+a_{j+2}+a_{j+3}+...+a_i\equiv 0 \pmod{n}$$