# Sum of consecutive sub-sequence of 100 natural numbers divides 100 (equals 0 mod 100) [duplicate]

Possible Duplicate:
pigeonhole principle and division

I need a little help in an exercise. Given 100 natural numbers $a_{1},..,a_{100}$ , prove that there is a consecutive sub-sequence $a_{i} , a_{i+1} , ... , a_{j}$ such that $a_{i} + a_{i+1} + ... +a_{j} = 0 \mod 100$

Well, because

$(a_{i} + a_{i+1} + ... +a_{j}) \mod 100 = (a_{i} \mod 100) + (a_{i+1} \mod 100) + ... + (a_{j} \mod 100)$

I can assume that all the elements in the sequence are between $1$ to $100$.

Anyhow, I tried to think about it and I didn't manage to prove that :(

I thought at the beginning I should use pigeonhole principle but it didn't work out for me. Any clues anyone?? Thanks :)

-

## marked as duplicate by Amr, Thomas Andrews, Henry T. Horton, Davide Giraudo, FabianDec 30 '12 at 23:02

Consider the $101$ numbers $s_n=a_1+\ldots + a_n$, $0\le n\le 100$. By the pigeon-hole principle, two of them are congroent modulo $100$, say $s_i\equiv s_j\pmod{100}$ with $0\le i<j\le 100$. What can you say about $s_j-s_i$?