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

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.

Originally Posted by waddlyeli

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 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...

Ah, I see. If two of the sums add up to numbers in the same equivalence class, then clearly subtracting the smaller sum from the bigger sum results in a number congruent to n, modulo n.

This nice little theorem is due to Erdös.