002. The Subset Sum Multiple of n

Given the set $A = \{ a_1, a_2, \cdots, a_n \}$ for $a_i \in \mathbb{Z}$ where all elements are distinct, prove that there exists a subset of $A$ whose sum is multiple of $n$ except for the empty set.

---

Consider the following $n$ values, $$\begin{aligned} &a_1, \\ &a_1 + a_2, \\ &a_1 + a_2 + a_3, \\ &\qquad \vdots \\ &a_1 + \cdots + a_n \end{aligned}$$

In the case that there exists a value multiple of $n$ among these values, it is trivial. Assume that there does not exist that. By pigeonhole principle, there must exist at least two values that have an equal remainder when divided by $n$. Let these two values be $a_1 + \cdots + a_i$ and $a_1 + \cdots + a_j$ where $i < j$. Then the subtraction of them, $a_{i + 1} + \cdots + a_j$, is multiple of $n$. Since $\{ a_{i + 1}, \cdots, a_j \}$ is not the empty set, this completes the proof.