002. The Subset Sum Multiple of n

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

Consider the following nn values, a1,a1+a2,a1+a2+a3,a1++an\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 nn 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 nn. Let these two values be a1++aia_1 + \cdots + a_i and a1++aja_1 + \cdots + a_j where i<ji < j. Then the subtraction of them, ai+1++aja_{i + 1} + \cdots + a_j, is multiple of nn. Since {ai+1,,aj}\{ a_{i + 1}, \cdots, a_j \} is not the empty set, this completes the proof.

© 2024. All rights reserved.