Results 1 to 2 of 2

Thread: 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 $\displaystyle A$ of $\displaystyle N=\{1,...,n\}$ , let $\displaystyle \mu(A)=\sum_{a \in A}a$. Then $\displaystyle 0 \leq\mu(A) \leq n\mid A \mid$ because $\displaystyle A$ contains $\displaystyle \mid A \mid$ elements all less than or equal to $\displaystyle n$.

    Now since $\displaystyle S$ has $\displaystyle 2^k$ subsets, and there are at most $\displaystyle \mu(S) \leq kn$ values of $\displaystyle \mu (S')$ where $\displaystyle S'$ is any subset of $\displaystyle S$, and since we suppose $\displaystyle 2^k > kn$, then two of the values $\displaystyle \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: Apr 19th 2010, 10:31 AM
  2. Subsets of Non-Measurable sets
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: Mar 14th 2010, 10:03 AM
  3. Sets and subsets relationships
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 28th 2009, 12:55 PM
  4. Sets & Subsets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Jan 21st 2009, 03:57 PM
  5. subsets/open sets
    Posted in the Calculus Forum
    Replies: 1
    Last Post: Mar 12th 2007, 09:27 AM

Search Tags


/mathhelpforum @mathhelpforum