# Math Help - Pigeon Hole Principle

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

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

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