Indian Statistical Institute B.Math & B.Stat : Number Theory

Let $a_1,a_2,_3, \dots ,a_n$ be integers. Show that there exists integers $k$ and $r$ such that the sum $$a_k+a_{k+1}+\dots +a_{k+r}$$ is divisible by $n.$ We construct a finite sequence of partial sum of the given finite sequence as follows, $$s_1 = a_1$$ $$s_2 = a_1+a_2$$ $$s_3 = a_1+a_2+a_3$$ $$\dots$$ $$s_n = a_1+a_2+ \dots +a_n$$ If $s_i \equiv 0(mod \quad n)$ for any admissible value of $i$ then we are done with $k= 1 \quad and \quad r= i-1$. Therefore assume $s_i \not\equiv 0(mod \quad n) \quad \forall \quad i \in \{1,2,\dots,n\} \implies s_i \equiv k(mod \quad n)$ where $1 \leq k \leq n-1, k \in \mathbb{N} .$ Since there are $n$ such congruences and $n-1$ possible values of $k$, $Pigeon-Hole$ principle asserts that at least two different partial sums have the same remainder, i.e, $s_i \equiv k(mod \quad n) \quad s_j \equiv k(mod \quad n)$ for $i \neq j$. Therefore $s_i \equiv s_j(mod \quad n)$ (Without loss of generality assume that $i > j$ ) $\implies s_i-s_j \equiv 0(mod \quad n)$ $\implies s_{j+1}+s_{j+2}+\dots +s_{j+i-j} \equiv 0(mod \quad n)$ This is what was asked!