Results 1 to 3 of 3

Math Help - Pigeon hole principle

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    5

    Pigeon hole principle

    I have problem with this questions:

    How many different 5-element subsets can be formed from the set {1,2,3,4,5,6,7,8,9}? Two elements of the original set are said to form S-pair if their sum is equal to 10. Show that every 5-element subset that does not contain an S-pair must contain 5. How many subsets will not contain any S-pairs? Give a list of all such subsets.
    [Hint:using pigeon hole principle and inclusion-exclusion principle].

    Can anybody help!!!
    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

    Pigeon-hole principle

    Hello epi1988
    Quote Originally Posted by epi1988 View Post
    I have problem with this questions:

    How many different 5-element subsets can be formed from the set {1,2,3,4,5,6,7,8,9}? Two elements of the original set are said to form S-pair if their sum is equal to 10. Show that every 5-element subset that does not contain an S-pair must contain 5. How many subsets will not contain any S-pairs? Give a list of all such subsets.
    [Hint:using pigeon hole principle and inclusion-exclusion principle].

    Can anybody help!!!
    The number of 5-element subsets is the number of ways of selecting 5 items from 9 = \binom{9}{5}=126.

    The original set A = {1, 2, ..., 9} may be partitioned into 5 subsets: the four subsets comprising S-pairs: {1, 9}, {2, 8}, {3, 7} and {4, 6}, and the subset {5}. Suppose now that B is a 5-element subset that does not contain any S-pairs. Then B contains exactly one element from each of the 5 subsets in the above partition, since otherwise it will contain an S-pair. Therefore B contains the element 5.

    To find the number of subsets containing no S-pairs: the element from each of the four S-pair subsets in this partition of A can be chosen in 2 ways, and the fifth element (5) in 1 way. So there are 2^4 \times 1 = 16 such subsets altogether.

    These subsets are {1, 2, 3, 4, 5}, {9, 2, 3, 4, 5}, ... ?

    I think you can complete it now.

    Grandad
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2009
    Posts
    5

    Thumbs up pigeon hole principle

    Thanks grandad..
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 18th 2011, 05:24 AM
  2. Pigeon Hole Principle
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 28th 2009, 08:22 PM
  3. Pigeon Hole Principle Help!
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 17th 2008, 12:14 AM
  4. pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 16th 2008, 04:39 AM
  5. Pigeon Hole Principle
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 8th 2007, 06:37 PM

Search Tags


/mathhelpforum @mathhelpforum