Results 1 to 2 of 2

Math Help - disjoint subsets

  1. #1
    Newbie
    Joined
    May 2010
    Posts
    4

    disjoint subsets

    Let S be a set of 6 random positive integers whose sum is not bigger than 60.
    Show that in any such set S there exists two non-empty , disjoint subsets whose elements have the same sum.


    I've tried to somehow use the pigeon hole principle but I'm STUCK.

    I know there are 2^6 possible subsets...though the empty set and the set with all six elements should be thrown away....which leaves us with 62 subsets.

    Can anyone help me or "nudge" me in the right direction ?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    May 2010
    Posts
    4
    actually it was simpler than I could imagine.
    there are 62 possible subsets...and only 59 possible sums for these.
    so clearly at least 2 subsets have the same sum.

    if the subsets are disjoint...we are done.
    if the subsets share one or more elements...then we remove the shared elements ..and voilá .. we have our disjoint subsets with equal sums.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. 2 disjoint clsed subsets of (R^2)
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: August 28th 2011, 04:09 AM
  2. [SOLVED] Set related question ... find out if disjoint of not disjoint ...
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: July 9th 2011, 02:26 AM
  3. Replies: 5
    Last Post: March 10th 2011, 08:22 AM
  4. Disjoint subsets countable
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: July 20th 2010, 01:41 PM
  5. Subsets that have a disjoint
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 8th 2010, 10:02 AM

Search Tags


/mathhelpforum @mathhelpforum