Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

Just a language point: you mean "is divisible by," not "divides" – Thomas Andrews Dec 30 '12 at 22:14
up vote 1 down vote accepted

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$?

share|cite|improve this answer
Thanks a lot :) – John Smith Dec 30 '12 at 22:16

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