Results 1 to 5 of 5

Math Help - Discrete Math, Pigeon Hole Principle/Sum of Elements of Subsets

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    3

    Discrete Math, Pigeon Hole Principle/Sum of Elements of Subsets

    Ok, so the question is to show for any set A of positive integers taken from {1,2,...,12}, A must contain two disjoint subsets whose elements when added up give the same sum.

    Now, reading around on this site, what I have so far is that there are 2^6 possible subsets of a 6-element set, and the maximum possible sum is 57. I believe I'm supposed to then use the pigeon hole principle to show that it is true, but I'm not sure how to calculate the amount of disjoint subsets that have the same sum, which I'm thinking I have to find. Can someone help me out please?
    Follow Math Help Forum on Facebook and Google+

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

    More information please

    Hello therpgmaker

    Welcome to Math Help Forum!

    Sorry, but I don't think this question makes sense, as you have stated it.
    for any set A of positive integers taken from {1,2,...,12}
    There must be a minimum number of elements in A, otherwise it is clearly untrue that
    A must contain two disjoint subsets whose elements when added up give the same sum
    For instance if A = {1}, the only subsets of A are \oslash and A itself.

    Grandad
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2009
    Posts
    3
    Oh, crap, I left out an important piece of information. It's for any set of six positive integers taken from 1 to 12.
    Follow Math Help Forum on Facebook and Google+

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

    Pigeon-hole principle

    Hello therpgmaker

    You have nearly all the bits you need to solve this problem now. You've said that the maximum sum that can be made with 6 of the elements of {1, 2, ..., 12} is 57. So there at most 58 different sums (0 through 57) that can be made by adding the elements of a subset of A, where A is itself a subset of six elements from {1, 2, ..., 12}.

    And, as you said, any set A that contains 6 elements has 2^6 = 64 distinct subsets. So by the pigeonhole principle, the elements of at least two of these subsets must have the same sum.

    The only question that remains is: can we prove that A has two disjoint subsets with the same 'element-sum'? Yes. Since if P and Q are two subsets of A with the same element-sum, then the sets (P - Q) and (Q - P) will also have the same element sum, because the same elements (those common to both P and Q) have been removed. And, of course, (P - Q) and (Q - P) are disjoint.

    That completes the proof.

    Grandad
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Mar 2009
    Posts
    3
    Thanks for your help.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Pigeon-hole Principle (3)
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 5th 2011, 10:22 AM
  2. [SOLVED] Pigeon-hole Principle (2)
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: August 3rd 2011, 02:40 PM
  3. [SOLVED] pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 18th 2011, 05:24 AM
  4. Pigeon Hole Principle
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 28th 2009, 08:22 PM
  5. Pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 9th 2009, 03:56 AM

Search Tags


/mathhelpforum @mathhelpforum