Given N integers a₁, a₂, ... a_N prove there exists a (non empty) subset whose sum is a multiple of N. (Allow repeated numbers in both the original set and its subsets.)

Consider the N sums
a₁
a₁ + a₂
...
...
a₁ + a₂ + ... + a_n

If no two of these N sums have the same residue mod N, then one of the sums has residue 0 mod N, and we are done.

Otherwise, 2 of these sums have the same residue mod N, and we can take their difference.

Posted by Tan Kiat Chuan on 2005-08-26 04:20:11