5
$\begingroup$

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.

$\endgroup$
2

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ A ha! So two of these sums will have the same remainder, so their difference is divisible by p, right? $\endgroup$ Commented Sep 30, 2012 at 17:38
  • $\begingroup$ @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. $\endgroup$ Commented Sep 30, 2012 at 17:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .