# Pigeon Hole Principle

• October 28th 2009, 05:59 PM
Pigeon Hole Principle
I'm pretty sure that I should apply the pigeon hole principle, but I'm not sure exactly how.
Let a_i with i ranging from 1 through n be a sequence of integers (both positive and negative, not necessarily all different). Prove that there exists integers j and k with 1 <= j <= k <= n such that the sum starting from a_j and ending at a_k (ie, the sum of some subsequence of the sequence) sums to a multiple of n
• October 28th 2009, 06:02 PM
Perhaps we consider the remainders of the members of the sequence after we divide by n. The only possible values for remainders are less than n and greater than 1 (otherwise, we'd be done), and we have n numbers, so at least two members of the sequence have the same remainder.
• October 28th 2009, 06:12 PM
awkward
Quote:

I'm pretty sure that I should apply the pigeon hole principle, but I'm not sure exactly how.
Let a_i with i ranging from 1 through n be a sequence of integers (both positive and negative, not necessarily all different). Prove that there exists integers j and k with 1 <= j <= k <= n such that the sum starting from a_j and ending at a_k (ie, the sum of some subsequence of the sequence) sums to a multiple of n

Hint:

Consider the n sums $\sum_{i=1}^j a_i$ for j = 1, 2, ..., n.

If any one of these sums is zero, modulo n, we are done. Otherwise, each of the sums must fall in one of the congruence classes 1, 2, ..., n-1 modulo n. There are n sums and only n-1 congruence classes, so there must be some congruence class that contains at least two of the sums. And then...
• October 28th 2009, 08:21 PM