# 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.