3
$\begingroup$

This question already has an answer here:

Given any 30 positive integers, prove that we can find some integers so their sum is divisible by 30. I don't know where to start. Please some hints.

$\endgroup$

marked as duplicate by Joel Reyes Noche, JMP, Joey Zou, Jack's wasted life, loup blanc Sep 30 '16 at 8:55

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.

  • $\begingroup$ It is an edited dublicate, it was me that wrote that problem, but for some reasons I couldnt login with that account $\endgroup$ – A.LIE Sep 29 '16 at 21:54
  • $\begingroup$ Impatient of me, sorry. $\endgroup$ – Calum Gilhooley Sep 29 '16 at 21:57
  • $\begingroup$ Its ok. No problem. $\endgroup$ – A.LIE Sep 29 '16 at 22:09
1
$\begingroup$

Hint: consider congruences modulus 30...

$\endgroup$
1
$\begingroup$

A number is divisible by $30$ if it equals $0$ mod $30$. Can you take it from here? (More answer below)

Pick any $30$ numbers and add them together one by one, keeping a running total. If at any point we get (a) $0$ mod $30$, or (b) the same value mod $30$ as we did earlier, we've won. In case (a), we have the sum in hand. In case (b), we subtract out the numbers before we reached that value the first time, and the sum of what's left will be divisible by $30$. Because we have $30$ integers, even if we never repeat, one of the sums has to be $0$ mod $30$ by the pigeonhole principle.

$\endgroup$

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