# Prove that any set of 2015 numbers has a subset who's sum is divisible by 2015

I assume this is correct to any size set, not 2015 in particular... it's obviously true for 2. I know from pen and paper it's true for 3, and 4....

I understand that I should look at the reminders, and build pigeonholes from them. If one of the numbers has a 0 reminder obviously the entire set is divisible, so the possible reminders go from 1 to (n-1). i have n numbers hence one of the reminders repeats. the sums of the reminders go from 1 to n*(n-1)....

And that's it...

Any and all help would be appreciated.

Of course I mean non empty set...

• You probably mean "non-empty subset". Any set of numbers of any size has the empty set as a subset, which has a sum of zero, which is divisible by 2015. – hvd Jan 24 '15 at 22:33
• @hvd off course – AK_ Jan 26 '15 at 12:03

Let the set be $\{a_1,a_2\dots a_{2015}\}$

consider the sets $\{a_1\},\{a_1,a_2\},\{a_1,a_2,a_3\}\dots \{a_1,a_2\dots a_{2015}\}$

If one is a multiple of $2015$ we are done, if not two must have the same congruence, suppose $\{a_1,a_2\dots a_j\}$ and $\{a_1,a_2\dots a_h\}$ have the same congruence with $h<j$, then the set $\{a_{j+1},a_{j+2}\dots a_{h}\}$ has a sum that is multiple of $2015$.

The reason we took those sets is that they are a chain under inclusion, so we can subtract one from the other.

• You really should complete your answer. For one, you didn't put any "Hint" disclaimer, so this is definitely incomplete. – Matt Samuel Jan 24 '15 at 21:32
• can you explain what does congruence means? – AK_ Jan 24 '15 at 21:42
• It means they leave the same remainder when you divide by 2015 – Jorge Fernández Hidalgo Jan 24 '15 at 21:43
• Cool.... such a simple answer... I've been working on it for the last couple of hours... – AK_ Jan 24 '15 at 22:16

Hint: Look at $a,a+b,a+b+c,a+b+c+d,...$