Sum of a subset of a set of cardinality n being a multiple of n

Question

If I have a set of cardinality n, how do I know that there exists a subset that the sum of the elements in the set are a multiple of n.

$\forall S\subseteq \mathbb{Z} : |S|=n$

$\exists A \subseteq S : \sum_i A_i = nk, k \in \mathbb{Z}$

Answer 1

(This is not original.)

List them in some order $(A_i)_{i=1}^n$ and let $B_j =\sum_{i=1}^j A_i $ for $j=1$ to $n$.

If all the $B_j$ are distinct mod $n$, then, since there are $n$ of them, one of then is $\equiv 0 \bmod n$.

If two of them are equal $\bmod n$, say $B_k \equiv B_j$ where $j < k$, then, since $B_j =\sum_{i=1}^j A_i $ and $B_k =\sum_{i=1}^k A_i $, subtracting these, $0 \equiv B_k-B_j \equiv\sum_{i=j+1}^k B_j $ so the sum of $(A_i)_{i=j+1}^k$ is divisible by $n$.