9
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – hvd Jan 24 '15 at 22:33
  • $\begingroup$ @hvd off course $\endgroup$ – AK_ Jan 26 '15 at 12:03
18
$\begingroup$

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.

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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