Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A cool question

  1. Sep 22, 2007 #1


    User Avatar
    Gold Member

    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. jcsd
  3. Sep 22, 2007 #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.
  4. Sep 22, 2007 #3
    can this subset be 1 number? or does it have to be summable?
  5. Sep 22, 2007 #4


    User Avatar
    Gold Member

    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.
  6. Sep 22, 2007 #5


    User Avatar
    Science Advisor

    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".
  7. Sep 22, 2007 #6


    User Avatar
    Science Advisor
    Homework Helper

    The result holds for sets. daniel_i_l's point was surely that the result naturally extends to multisets.
  8. Sep 22, 2007 #7


    User Avatar
    Science Advisor
    Homework Helper

    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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Threads - cool question Date
B Secondary Upper and Lower Bound QUESTION Mar 10, 2018
B Percentage of antifreeze in cooling system Jul 15, 2016
I Cool Parametric Equations Mar 24, 2016
A cool identity Feb 25, 2014
Sharing a cool series Aug 29, 2013