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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Hint : Consider the remainders when you divide the positive integers by 2016 $\endgroup$ – rsadhvika Feb 18 '18 at 11:14
  • $\begingroup$ 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? $\endgroup$ – Alon Weissfeld Feb 18 '18 at 11:25
  • $\begingroup$ 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. $\endgroup$ – rsadhvika Feb 18 '18 at 11:37
  • $\begingroup$ 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. $\endgroup$ – rsadhvika Feb 18 '18 at 11:41

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.

  • $\begingroup$ I still don't see it.. can you elaborate? Don't we need just the "0 remainder" subset? $\endgroup$ – Alon Weissfeld Feb 18 '18 at 11:29
  • $\begingroup$ There are only 2016 remainders and you have 2016 members in the set that I have defined. If all remainders are different ,one remainder is zero,and you are done. Otherwise two remainders must be the same. Then look at the difference and you will have your set of zero remainder. $\endgroup$ – Mohammad Riazi-Kermani Feb 18 '18 at 12:20

Not the answer you're looking for? Browse other questions tagged or ask your own question.