Prove that for any set of $n$ integers, there exists a nonempty subset whose elements sum to a multiple of $n$.

Question

I have read various proofs for similar questions, but I cannot picture what is being said. Can anyone break this proof down, or show a simple discrete example along with the proof?

Answer 1

Consider the successive sums of the first number you happened to pick, the first and the second, etc. You get a succession of $n$ partial sums. If one of them is divisible by $n$, you are done. Otherwise you have $n$ partial sums with only $n-1$ possible remainders when divided by $n$. So take two with the same remainder. Their difference...which is the sum of the numbers that are in the longer sum but not the shorter, is divisible by $n$. QED

For example if $n=4$ and you take 1, 9, 5, 7, your partial sums are 1, 1+9=10, 1+9+5=15, and 1+9+5+7=22. The remainders mod 4 are 1, 2, 3, and 2. The second and fourth sums have the same remainder, so their difference...namely 5+7...is divisible by 4.