Results 1 to 3 of 3

Math Help - Sets

  1. #1
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5

    Sets

    S\subset\mathbb{N}_{99} that contains 10 elements. Use the Pigeonhole Principle to prove that there exists two disjoint subsets of S whose elements have the same sum.

    Don't know what to do.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Failure's Avatar
    Joined
    Jul 2009
    From
    Zürich
    Posts
    555
    Quote Originally Posted by dwsmith View Post
    S\subset\mathbb{N}_{99} that contains 10 elements. Use the Pigeonhole Principle to prove that there exists two disjoint subsets of S whose elements have the same sum.

    Don't know what to do.
    I suppose you have to show that there are more disjoint subsets of S than there are possible different sums of the elements of those subsets. So the first question to answer is how many different disjoint subsets of S there are.
    Next, if you are lucky and there are a sufficiently large number of disjoint subsets of S, you might be able to use a very rough estimate of how many different sums there could possibly be (like, for example, 10\cdot 99).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by Failure View Post
    I suppose you have to show that there are more disjoint subsets of S than there are possible different sums of the elements of those subsets. So the first question to answer is how many different pairs of disjoint subsets of S there are.
    Next, if you are lucky and there are a sufficiently large number of pairs of disjoint subsets of S, you might be able to use a very rough estimate of how many different sums there could possibly be (like, for example, 10\cdot 99).
    To be honest, I don't know what really needs to be shown. Let alone how to go about it.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. What are Positive Sets, Ultimate Sets?
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: November 29th 2011, 04:11 PM
  2. Open sets and sets of interior points
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: August 9th 2011, 03:10 AM
  3. Metric spaces, open sets, and closed sets
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: March 16th 2011, 05:17 PM
  4. Replies: 9
    Last Post: November 6th 2010, 12:47 PM
  5. Approximation of borel sets from the top with closed sets.
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: February 18th 2010, 08:51 AM

Search Tags


/mathhelpforum @mathhelpforum