Sum of a subset of a set of cardinality n being a multiple of n 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}$

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