Prove for every set of n integers there is a nonempty subset

Prove for every set of n integers, there is a nonempty subset that sums to a multiple of n.

Solution

Let a₁, a₂, ....,a_n be a set of n positive integers.
Denote S1=a1, S₂=a₁+a₂, ..., Sn=a₁+a₂+.....+a_n. Suppose that none of these sums is divisible by n.
The sums give at most n-1 distinct remainders when divided by n, namely, 1,2,.....n-1. But since there are n sums, at least two of them have the same remainder when divided by n, say S_i and S_j, where j > i. Now S_j - S_i is divisible by n and also S_j - S_i = a_i+1 + .....+ a_j .