Proving that a set of 2016 natural numbers contain a non-empty set with a sum divisible by 2016

Question

Prove: Each set which consists of 2016 natural numbers contains a non-empty set that has a sum divisible by 2016

My attempt: Use the pigeonhole principle. Let $A$ be a set of 2016 natural numbers. I'll split the answer to two different possibilities:

1. $A$ contains at least one number which is divisible by 2016. In this case the claim is true.

2. $A$ does not contain numbers that are divisible by 2016. In this case, we'll apply the pigeonhole principle.

   • Holes: $\{1,2,3,4,...,2016\}$, A set of all possible remainders when dividing a number (which is not divisible by 2016) by 2016. In total there are 2015 holes.
   • Pigeons: 2016 numbers.

   Each number will be divided by 2016 and put into the appropriate hole according to the that number's division remainder. By the pigeonhole principle, at least in one hole will be $\lceil \frac{2016}{2015} \rceil$. objects. In this case, the claim is also true.

Is my proof sufficient? Can I prove this not using 2 different possibilities, or maybe not using the pigeonhole principle?

Edit: As stated in the comments and in the answers, my proof is false. The proof shows that there exists at least 2 numbers in the set $A$ with a difference divisible by 2016. It does not prove that there is a non-empty set with a sum divisible by 2016.

Answer 1

Label the numbers $a_1, a_2, \dots a_{2016}$ in any order. Now consider the sums:

$$b_1 = a_1$$ $$b_2 = a_1 + a_2$$ $$b_3 = a_1 + a_2 + a_3$$ $$ \cdots$$ $$b_{2016} = a_1 + a_2 + \cdots + a_{2016}$$

Now if any of the $b$'s is divisivle by $2016$ we are done. Otherwise we have $2015$ positive remainders (pigeonholes) and $2016$ numbers (pigeons) so we have that there exist two different numbers $b_i$ and $b_j (i>j)$ s.t. $2016 \mid b_i - b_j = a_{i+1} + a_{i+2} + \cdots + a_j$

So the wanted subset is $\{a_{i+1}, a_{i+2}, \dots, a_j \}$. Hence the proof.

As noted in the comments your proof isn't complete, but also I can't see a way how you can proceed from there.

For your further questions as in my proof we don't need to consider two different cases, but Pigeonhole Principle is required. In general I can't see a proof without Pigeonhole Principle, as simply there are too many cases to be considered.