A cool question

1. Sep 22, 2007

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!

2. Sep 22, 2007

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.

3. Sep 22, 2007

ice109

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

4. Sep 22, 2007

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.

5. Sep 22, 2007

HallsofIvy

Staff Emeritus
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".

6. Sep 22, 2007

CRGreathouse

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

7. Sep 22, 2007

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.