0
$\begingroup$

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 :)

  • 3
    Just a language point: you mean "is divisible by," not "divides"2012-12-30

1 Answers 1

1

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. What can you say about $s_j-s_i$?