Divisibility Problem: Prove Existence of $i,j$

[qamaz]

$$\text{ Let } n∈N \text{ and } (a1,a2,…,a_{n})∈\mathbb{Z}^{n}.

\text{ Prove that always exist } i,j∈ \underline{n} \text{ with } i≤j \text{ so }

\sum\limits_{k=i}^{\\j} a_{k} \text{ divisible by n} .$$

 

[Evgeny.Makarov]

Hi, and welcome to the forum!

Hint: Consider \(\displaystyle b_j=\sum_{k=1}^ja_k\), $j=1,\ldots,n$ and apply the pigeonhole principle to remainders when $b_j$ are divided by $n$.

 

[qamaz]

What is the meaning of $$\mathbb{Z}^{n}$$?

 

[Evgeny.Makarov]

\(\displaystyle \mathbb{Z}\) denotes the set of integers. If $A$ and $B$ are sets, $A\times B$ denotes the set of all ordered pairs, where the first element comes from $A$ and the second one comes from $B$. More generally, $A_1\times \dots\times A_n$ denotes the set of all $n$-tuples, i.e., of ordered sequences of length $n$, where the $i$th element comes from $A_i$ for $i=1,\ldots,n$. Finally, $A^n=A\times\dots\times A$ ($n$ times). Thus, \(\displaystyle (a_1,\ldots,a_n)\in\mathbb{Z}^n\) means that all $a_i$ are integers.