5

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.

Michael Hardy
  • 1
  • 31
  • 294
  • 591
user1526710
  • 121
  • 1
  • 7
  • You may find of interest [a similar Pigeonhole argument:](http://math.stackexchange.com/a/163827/242) 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
  • See also: http://math.stackexchange.com/questions/1933631/prove-that-there-are-i-and-j-with-1-le-i-le-j-le-n-such-that-a-ia – Martin Sleziak Nov 21 '16 at 04:14

1 Answers1

5

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.

Ross Millikan
  • 369,215
  • 27
  • 252
  • 444