Take the 2-minute tour ×
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.

Given a sequence of $p$ integers $a_1, a_2, \ldots, a_p$, show that there exist consecutive terms in the sequence whose sum is divisible by $p$. That is, show that there are $i$ and $j$, with $1 \leq i \leq j \leq p$, such that $a_i + a_{i+1} + \cdots + a_j$ is divisible by $p$.

I'm having trouble with labeling which entities are the pigeons, and which are the pigeonholes. I think somewhere down the line, there has to be more different sums than $p$, but that is just a guess.

share|improve this question
    
You may find of interest a similar Pigeonhole argument: if $\rm\:n\:$ is coprime to $10\,$ then every integer with at least $\rm\:n\:$ digits $\ne 0$ has a contiguous digit subsequence that forms an integer $\ne 0$ divisible by $\rm\:n.\ \ $ –  Bill Dubuque Sep 30 '12 at 18:29
add comment

1 Answer

up vote 2 down vote accepted

Hint: The holes are remainders on division by $p$. Consider $\sum_{i=1}^k a_i$ for $k=1,2,3 \ldots,p$ If any are divisible by $p$ you are done. If not, You have $p$ sums with only $p-1$ values of remainder allowed.

share|improve this answer
    
A ha! So two of these sums will have the same remainder, so their difference is divisible by p, right? –  user1526710 Sep 30 '12 at 17:38
    
@user1526710: Exactly. Then if the two that match are $k_1$ and $k_2$, the sum from $k1+1 through $k_2$ is the one you want. –  Ross Millikan Sep 30 '12 at 17:47
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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