Assume that $n \ge 1$ is an integer and that $a_1, a_2, ..., a_n$ is a sequence of $n$ integers. Prove that there are $i$ and $j$, with $1 \le i \le j \le n$, such that $a_i+a_{i+1}+ \cdots + a_j$ is divisible by $n$.

Here is what I have so far, I feel that I am very close to completing the proof, I just do not know how to finish it.

I am going to use the idea of the pigeonhole principle to prove this by assuming the opposite is true and finding a contradiction.
Let's assume there does not exist $i$ and $j$ such that $a_i+a_{i+1}+ \cdots + a_j$ is divisible by $n$

When we divide $a_i+a_{i+1}+ \cdots + a_j$ by $n$ there are $n-1$ remainders ($r$) we can get, $r={1, 2, \dots , n-1}$.
Now we look at the first $n$ possible sub sequences we can have when $i=1$, these are $(a_i), (a_i+a_{i+1}), \dots , (a_i+a_{i+1}+\dots+a_{i+n-1})$
By the pigeonhole principle when we divide each the sums of these sub sequences by $n$, since we have $n$ sub sequences and $n-1$ possible remainders, either one of them is divisible by $n$ or at least two of them share the same remainder. Let's call these two sums $a_h$ and $a_k$ where $a_k \gt a_h$.
Since $a_k$ and $a_h$ share the same remainder we can subtract them to get a number that is divisible by $n$, $a_k - a_h$ is divisible by $n$.

Now there is suppose to be a contradiction somewhere but I don't know what to do from here, why does this mean that there is an $i$ and a $j$ where $a_i+a_{i+1}+ \cdots + a_j$ is divisible by $n$?


Start with the sums: $$S_1=a_1\quad S_2=a_1+a_2\quad\cdots \quad S_n=a_1+\cdots +a_n$$

There are $n$ of these.

Case I. They are all different $\pmod n$

Then, as we have $n$ distinct classes $\pmod n$ we must hit them all, including $0$.

Case II. Two of them are congruent $\pmod n$.

Then if $S_k\equiv S_l\pmod n$ with $k>l$ we have $S_k-S_l\equiv 0 \pmod n$ but $S_k-S_l=a_{l+1}+\cdots +a_k$.

  • $\begingroup$ So in case two, $S_k-S_l$ will always equal the sum of another consecutive sub sequence, correct? That's what I was not sure about. $\endgroup$ – idknuttin Sep 20 '16 at 0:31
  • 1
    $\begingroup$ Yes. it's the consecutive sum between $a_{l+1}$ and $a_k$. $\endgroup$ – lulu Sep 20 '16 at 0:32

consider the $n+1$ numbers $$b_0=0,$$ $$b_1=a_1,$$ $$b_2=a_1+a_2,$$ $$\dots$$ $$b_n=a_1+a_2+\dots +a_n.$$ There must be two of them, say $b_i,b_j$ such that $b_i\equiv b_j $ mod $n$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.