Thread: 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!!!

Hello epi1988

Originally Posted by epi1988

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 = $\displaystyle \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 $\displaystyle 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

Thanks grandad..