Using Pigeonhole principle to prove a subset statement [duplicate]

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?

marked as duplicate by Stefan4024, Community♦Feb 18 '18 at 14:47

• Hint : Consider the remainders when you divide the positive integers by 2016 – rsadhvika Feb 18 '18 at 11:14
• I've thought about it - we have 2016 remainders (0, 1, 2, ..., 2015) that determine the "containers" so I assume we'll have it least one subset that belongs to the "0 reminders" container... Are the items are the subsets defined by the power set of the parent group? – Alon Weissfeld Feb 18 '18 at 11:25
• Consider the set given by Mohammad in the answer. Notice that when you don't get the remainder 0 for any element in that set, at least two elements give the same remainder. This means the difference is divisible by 2016. the elements in the desired subset are the elements that contribute to the result after the subtraction. – rsadhvika Feb 18 '18 at 11:37
• For example, if $a_1$ and $a_1+a_2+a_3$ give the same remainder, then the sum $a_2+a_3$ is divisible by 2016. – rsadhvika Feb 18 '18 at 11:41

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