Prove that there exists at least one subset of the set $A=\{a_1,a_2,a_3,\dots,a_n\}$ such that the sum of its members is divisible by n.

Question

$A$ is a set of $n$ arbitrary natural numbers.

We know that $|A|=n$, so $\forall a_i\in A; a_i=nq+j(i)\ \ \ \ (0\le j(i)\lt n)$.

If there exists an $a_k$ such that $j(k)=0$, then the subset $\{a_k\}$ is the answer.

If not, then $\forall a_i\in A; a_i=nq+j(i)\ \ \ \ (0\lt j(i)\lt n)$.

Then I can say there exist at least two members of $A$ such that $n \mod a_a=n\mod a_b$.

But I can't go further. Help needed.

---

Guys sorry. It's "divisible by $n$". :-shame

Answer 1

Hint 1:

Consider $a_1,a_1+a_2,...$

Hint 2:

Use the Pigeonhole Principle.

Answer 2

Hint 1

If the $n$ numbers $a_{1}, a_{1} + a_{2}, \dots, a_{1} + \cdots + a_{n}$ are distinct modulo $n$, then one of them is congruent to $0 \pmod{n}$.

Hint 2

If two of them are congruent modulo $n$, consider the second one (longer sum) minus the first one (shorter sum).