Using Pigeonhole principle to prove a subset statement

Question

I'm trying to solve the following question:

Prove: For every set of 2016 natural positive numbers there is a non-empty subset such that the sum of its elements is divisible by 2016.

It feels to me that this statement is valid for every natural number (other than 2016) and could be proven by the Pigeonhole Principle. I've tried to scale down the problem, but no luck.

Any suggestions?

Answer 1

Look at the set $$ \text {{$a_1, a_1+a_2, a_1+a_2+a_3, ....$}}$$

There are 2016 elements so either one of them is divisible by 2016 or two of them have the same remainder.

In any case you have your result.