Results 1 to 8 of 8

Math Help - pigeon-hole

  1. #1
    Member
    Joined
    Sep 2008
    Posts
    76

    pigeon-hole

    Let S be a set of ten integers chosen from 1 through 50. Show that the
    set has at least two different (but not necessarily disjoint) subsets
    of exactly four integers each that add up to the same number. (For
    instance, if S = {3,8,9,18,24,34,35,41,44,50} then the subsets can be
    taken to be {8,24,34,35} and {9,18,24,50}; these borth have sums of
    101.Show this using the pigeonhole principle.

    I'm clueless
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,643
    Thanks
    1594
    Awards
    1
    From a set of ten elements, how many subsets of four elements are possible: Pigeons?
    Note that 1 + 2 + 3 + 4 = 8\,\& \,47 + 48 + 49 + 50 = 194.
    That means the minimum sum of four is 8, maximum is 194; these are the pigeon holes.
    Put that together with the first question what do you see?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2008
    Posts
    76
    k so,

    for a set S of 10 integers, the number possible subsets of 4 elements = 10C4
    =70
    Do i also need to calculate the number of ways in which I can choose 10 elements between 1 to 50? and then m,ultiply it with 70?

    so, the number of elements in the pigeon = 70 (n)

    and the sum goes from 8 to 194.
    thus,the number of holes= 194 - 8 + 1 = 187 (m)

    n < m
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,643
    Thanks
    1594
    Awards
    1
    I don't mean to insult, but if you do not understand the basics here then there is no way to help you with these questions.
    \frac{{10!}}{{4!\left( {10 - 4} \right)!}} = \frac{{\left( {10} \right)\left( 9 \right)\left( 8 \right)\left( 7 \right)}}{{4!}} = 210.
    You need to know the basics here.
    If you don’t, then there is no need to ask for help.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Sep 2008
    Posts
    76
    oh well that was just a calculation mistake.I over looked something.Not to offend you either

    1+2+3+4 = 10 and not 8 (basics)

    Thanks,
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by Plato View Post
    From a set of ten elements, how many subsets of four elements are possible: Pigeons?
    Note that 1 + 2 + 3 + 4 = 8\,\& \,47 + 48 + 49 + 50 = 194.
    That means the minimum sum of four is 8, maximum is 194; these are the pigeon holes.
    Put that together with the first question what do you see?
    The problem statement did not say the integers are distinct.

    So the minimum sum is 1+1+1+1 and the maximum is 50+50+50+50.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,643
    Thanks
    1594
    Awards
    1
    Quote Originally Posted by NidhiS View Post
    Let S be a set of ten integers chosen from 1 through 50. Show that the set has at least two different (but not necessarily disjoint) subsets of exactly four integers each that add up to the same number.
    Quote Originally Posted by awkward View Post
    The problem statement did not say the integers are distinct. So the minimum sum is 1+1+1+1 and the maximum is 50+50+50+50.
    I completely disagree with you on that.
    How do you account for “subsets of exactly four integers each”?
    I do not count the collection [1,1,1,1] as subset.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by Plato View Post
    I completely disagree with you on that.
    How do you account for “subsets of exactly four integers each”?
    I do not count the collection [1,1,1,1] as subset.
    Yes, I guess you're right about that. Since the problem statement referred to a set of 10 integers and subsets of 4 integers, the implication is that set members are distinct.

    (The problem's conclusion still holds if the integers are not required to be distinct, however, but then to get the terminology correct the collections involved should be called multisets.)
    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, 09:22 AM
  2. [SOLVED] Pigeon-hole Principle (2)
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: August 3rd 2011, 01:40 PM
  3. [SOLVED] Pigeon-Hole Principle
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 30th 2011, 02:48 AM
  4. Pigeon Hole Principle
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 31st 2009, 07:59 AM
  5. Pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 9th 2009, 02:56 AM

Search Tags


/mathhelpforum @mathhelpforum