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

Question

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...

Answer 1

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.

Answer 2

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