Results 1 to 2 of 2

Math Help - Sets and subsets

  1. #1
    Newbie
    Joined
    Oct 2009
    From
    In limbo
    Posts
    18

    Sets and subsets

    Let k and n be integers satisfying n > k > 1. Let S be any set of k integers selected from 1,2,3,...,n. If 2^k > kn, prove that there exist two distinct nonempty subsets of S having equal sums of elements.


    I'm not sure how to prove this.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    For every subset A of N=\{1,...,n\} , let \mu(A)=\sum_{a \in A}a. Then 0 \leq\mu(A) \leq n\mid A \mid because A contains \mid A \mid elements all less than or equal to n.

    Now since S has 2^k subsets, and there are at most \mu(S) \leq kn values of \mu (S') where S' is any subset of S, and since we suppose 2^k > kn, then two of the values \mu (S_1), \mu (S_2) must coincide.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proving 2 sets are subsets of each other
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 19th 2010, 11:31 AM
  2. Subsets of Non-Measurable sets
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: March 14th 2010, 11:03 AM
  3. Sets and subsets relationships
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 28th 2009, 01:55 PM
  4. Sets & Subsets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 21st 2009, 04:57 PM
  5. subsets/open sets
    Posted in the Calculus Forum
    Replies: 1
    Last Post: March 12th 2007, 10:27 AM

Search Tags


/mathhelpforum @mathhelpforum