Results 1 to 8 of 8

Math Help - [SOLVED] Proof for equal sum subsets (pigeonhole principle)

  1. #1
    Newbie
    Joined
    Jan 2009
    Posts
    9

    [SOLVED] Proof for equal sum subsets (pigeonhole principle)

    Let S be a set of ten distinct positive integers, all less than 107. Prove that S has two distinct subsets that both have the same sum.

    So I've been racking my mind over this and I cannot figure out how to write a proper proof for it. I was thinking the pigeon hole principle might help out somehow, but I'm not entirely sure how. I'd be rather grateful to anyone who can help point me in the right direction.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    tah
    tah is offline
    Junior Member
    Joined
    Feb 2009
    Posts
    51
    Quote Originally Posted by sritter27 View Post
    Let S be a set of ten distinct positive integers, all less than 107. Prove that S has two distinct subsets that both have the same sum.

    So I've been racking my mind over this and I cannot figure out how to write a proper proof for it. I was thinking the pigeon hole principle might help out somehow, but I'm not entirely sure how. I'd be rather grateful to anyone who can help point me in the right direction.
    Are you sure that it's true, does it work for any set S ? In fact if S could be partition into two sets of the same sum, then sum of S has to be even !! but take S = {1,2,3,4,5,6,7,8,9,10} and sum S is 55, so this S could not be partitioned in such a way ...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Sum of subsets

    Hello everyone
    Quote Originally Posted by tah View Post
    Are you sure that it's true, does it work for any set S ? In fact if S could be partition into two sets of the same sum, then sum of S has to be even !! but take S = {1,2,3,4,5,6,7,8,9,10} and sum S is 55, so this S could not be partitioned in such a way ...
    The question doesn't say it's a partition - merely that the subsets are distinct. I don't know that we can assume that this even means that they are disjoint, simply that they are not equal.

    Having said that, I don't know how to tackle this question! But if I have any thoughts, I'll post them!

    Grandad
    Follow Math Help Forum on Facebook and Google+

  4. #4
    tah
    tah is offline
    Junior Member
    Joined
    Feb 2009
    Posts
    51
    Quote Originally Posted by Grandad View Post
    Hello everyoneThe question doesn't say it's a partition - merely that the subsets are distinct. I don't know that we can assume that this even means that they are disjoint, simply that they are not equal.

    Having said that, I don't know how to tackle this question! But if I have any thoughts, I'll post them!

    Grandad
    Ahh right i see.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Subsets

    Hello sritter27
    Quote Originally Posted by sritter27 View Post
    Let S be a set of ten distinct positive integers, all less than 107. Prove that S has two distinct subsets that both have the same sum.

    So I've been racking my mind over this and I cannot figure out how to write a proper proof for it. I was thinking the pigeon hole principle might help out somehow, but I'm not entirely sure how. I'd be rather grateful to anyone who can help point me in the right direction.
    A set with 10 elements has 2^{10} = 1024 distinct subsets.

    Maximum sum = 106 + 105 + ... + 97 = ...

    Minimum sum = 1 + 2 + ... + 10 = ...

    No of different sums = ...

    Can you supply the rest?

    Grandad

    PS. Sorry, that's not quite right. The minimum sum is zero - if the subset is the empty set.
    Last edited by Grandad; February 20th 2009 at 04:04 AM. Reason: Add PS
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Jan 2009
    Posts
    9
    Quote Originally Posted by Grandad View Post
    A set with 10 elements has 2^{10} = 1024 distinct subsets.

    Maximum sum = 106 + 105 + ... + 97 = ...

    Minimum sum = 1 + 2 + ... + 10 = ...

    No of different sums = ...

    Can you supply the rest?

    Grandad

    PS. Sorry, that's not quite right. The minimum sum is zero - if the subset is the empty set.
    Ah, I think it makes sense now.

    So if there are 1024 possible subsets of S and the maximum sum of S is 1015 then there are fewer possible sums than possible subsets. So, by the pigeonhole principle there must be two subsets of S that have the same sum? If that is true then if two subsets have the same sum but are not distinct (non-disjoint), they can be made distinct by removing the common elements between them and thus they would still have the same sum.

    Is this right?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Sum of subsets

    Hello sritter
    Quote Originally Posted by sritter27 View Post
    Ah, I think it makes sense now.

    So if there are 1024 possible subsets of S and the maximum sum of S is 1015 then there are fewer possible sums than possible subsets. So, by the pigeonhole principle there must be two subsets of S that have the same sum? If that is true then if two subsets have the same sum but are not distinct (non-disjoint), they can be made distinct by removing the common elements between them and thus they would still have the same sum.

    Is this right?
    Yes, you can certainly make the subsets disjoint in this way without affecting the equality of their sums, although the question doesn't actually say 'disjoint', merely distinct (which usually, of course, means 'not equal').

    Grandad
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Jan 2009
    Posts
    9
    Quote Originally Posted by Grandad View Post
    Yes, you can certainly make the subsets disjoint in this way without affecting the equality of their sums, although the question doesn't actually say 'disjoint', merely distinct (which usually, of course, means 'not equal').
    Okay, that makes sense. The problem was rewritten (not by me) from a book where it uses the term 'distinct' while the book uses the term 'disjoint', so I was using the terms interchangeably even those I realize I shouldn't.

    In any case, thank you for all the help.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. PigeonHole Principle
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: December 13th 2011, 05:25 AM
  2. subsets whose elements have equal sums (Pigeonhole)
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: August 7th 2010, 08:38 AM
  3. [SOLVED] Application of the Pigeonhole Principle
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: November 19th 2009, 05:47 PM
  4. Replies: 2
    Last Post: February 16th 2009, 07:30 AM
  5. Non-Trivial Proof Using Pigeonhole Principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 17th 2008, 11:26 PM

Search Tags


/mathhelpforum @mathhelpforum