Question 10: Let S1, S2, . . . , S50 be a sequence consisting of 50 subsets of the set {1, 2, . . . , 55}. Assume that each of these 50 subsets consists of at least seven elements. Use the Pigeonhole Principle to prove that there exist two distinct indices i and j, such that the largest element in Si is equal to the largest element in Sj .
Let [55] be the set with maximum element 55 ,
[54] be the set with maximum element 54 , and so on .....
Since every set has at least seven elements , Set [6] cannot exist since 6 cannot be the maximum of any element because if 6 is the maximum , elements less than or equal to 6 are 1,2,3,4,5,6 which are only 6 elements and weneed 7 to form a subset . Also therefore set [5] , set [4], set[3],set[2],set[1] cannot exists.
So sets which exist with different maximum are [7],[8] ,.........[55] which are 49 sets (pigeonholes)
Since we need to choose (S1 , S2 , ....S50 ) which are 50 sets (pigeons) from these 49 sets (pigeonholes),Using pigeonhole principle we can say that , atleast two sets will have the same maximum (two pigeons will be in the same pigeonhole).
Get Answers For Free
Most questions answered within 1 hours.