A cool question

  • Thread starter daniel_i_l
  • Start date
  • #1
daniel_i_l
Gold Member
867
0
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!
 

Answers and Replies

  • #2
2,063
2
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
1,707
5
can this subset be 1 number? or does it have to be summable?
 
  • #4
daniel_i_l
Gold Member
867
0
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
HallsofIvy
Science Advisor
Homework Helper
41,833
956
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
CRGreathouse
Science Advisor
Homework Helper
2,820
0
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.
 
  • #7
mathwonk
Science Advisor
Homework Helper
11,042
1,232
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.
 

Related Threads on A cool question

  • Last Post
Replies
9
Views
1K
  • Last Post
Replies
18
Views
3K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
3
Views
54K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
6
Views
17K
  • Last Post
Replies
11
Views
2K
Replies
8
Views
1K
  • Last Post
Replies
2
Views
3K
Replies
3
Views
1K
Top