Proving the Subset Sum Divisible by n

[daniel_i_l]

Prove that for every set of n numbers has a subset whose sum is divisible by n. I found this result very interesting. It's also fun to prove!

 

[neutrino]

Must these numbers be in sequence? Like {4,5,6,7,8}, or could it be any set like {1,10}?

EDIT: Never mind...that was a silly question.

 

[ice109]

can this subset be 1 number? or does it have to be summable?

 

[daniel_i_l]

Both the set and subset can be any not emty set. But I forgot to mention that numbers can repeat themselves so that in this case {1,1,2,2,4} is a "set" of 5 numbers and to answer ices's question, {1} is a subset of it.

 

[HallsofIvy]

No, that is NOT a "set" of 5 numbers! {1,1,2, 2,4}= {1, 2, 4} is a set of 3 numbers!
If you mean something else do not use the word "set".

 

[CRGreathouse]

No, that is NOT a "set" of 5 numbers! {1,1,2, 2,4}= {1, 2, 4} is a set of 3 numbers!
If you mean something else do not use the word "set".

The result holds for sets. daniel_i_l's point was surely that the result naturally extends to multisets.

 

[mathwonk]

work mod n. given n numbers, (integers), if we sum the first k of them, for k = 1,...,n, and we get n different numbers mod n, then one of them is congruent to n. done.if on the other hand two different sums have the same sum mod n , then subtracting them, gives a sum congr'uent to zero mod n. done again.