2
$\begingroup$

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.

$\endgroup$

marked as duplicate by Martin R, Community Jan 21 '18 at 12:38

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.

  • 3
    $\begingroup$ Case two, there are two numbers whose difference is a multiple of 2016, not their sum. You need to find different pigeons. $\endgroup$ – Michael Jan 21 '18 at 9:38
  • $\begingroup$ @Michael True, I did mix up sums and differences in my proof. I'll edit the post. $\endgroup$ – 0rka Jan 21 '18 at 9:43
  • $\begingroup$ No. How does the fact that one hole has multiple objects provr anything? $\endgroup$ – William Elliot Jan 21 '18 at 10:57
  • $\begingroup$ @WilliamElliot I did just say that my proof was flawed. I have yet been able to find a sufficient proof. So yes, for the time being my proof isn't true. $\endgroup$ – 0rka Jan 21 '18 at 11:01
  • $\begingroup$ I'm curious. Could it be done by induction? It's pretty easy to prove for n=1 :) $\endgroup$ – Eric Duminil Jan 21 '18 at 12:02
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If there isn't a $b_i | 1 \leq i \leq 2016$ divisible by 2016, doesn't that say that there isn't a subset in $\{a_1,a_2,...,a_{2016}\}$ with a sum divisible by 2016? $\endgroup$ – 0rka Jan 21 '18 at 11:08
  • $\begingroup$ @0rka No. Maybe the subset $\{a_3,a_5\}$ has sum divisible by 2016. Note that we didn't consider that subset in the subsets above. In fact the set has $2^{2016}$ and we have considered just $2016$ subsets. Indeed you can prove a stronger result. If the numbers are ordered in any order, then we can choose consecutive numbers whose sum is divisible by 2016. $\endgroup$ – Stefan4024 Jan 21 '18 at 11:14
  • $\begingroup$ The set actually has ${{2016}\choose{10}}$ subsets. I don't get why you can "choose consecutive numbers whose sum is divisible by 2016" when this is the one thing you are trying to prove. And you said that the numbers are ordered in any order, meaning that the subset $\{a_3,a_5\}$ can be reordered to be $\{a_1,a_2\}$. Have I misinterpreted something? $\endgroup$ – 0rka Jan 21 '18 at 11:19
  • 1
    $\begingroup$ Fine. More elegantly, instead of making "one of the $b$'s is divisible by $2016$" a separate case, you could have started with $b_0=0,$ and then you have $2017$ pigeons in $2016$ holes. $\endgroup$ – bof Jan 21 '18 at 11:20
  • 1
    $\begingroup$ @0rka The set actually has $2^{2016}$ subsets, as you can choose whether to include any element in the set or not. Also note that the ordering is predetermined at the beginning, so you can choose such consecutive numbers for any given ordering. In you reordering one of $b$'s would be divisible by $2016$ and we don't consider the case that none of the $b_i$ is divisible by $2016$. $\endgroup$ – Stefan4024 Jan 21 '18 at 11:26

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