4 votes 4 votes Show that if seven integers are selected from the first 10 positive integers, there must be at least two pairs of these integers with the sum 11. Attempt-:partition will be {(1,10),(2,9),(3,8)(4,7)(5,6)} now how to apply pigeonhole principle to find the answer? Combinatory pigeonhole-principle combinatory counting + – sourav. asked Aug 24, 2016 retagged Jun 27, 2017 by Arjun sourav. 2.1k views answer comment Share Follow See 1 comment See all 1 1 comment reply ashmita__shrivastava commented Jun 28, 2021 reply Follow Share Here randomly if we select any number from 1-10 for six times ex- number came such as 1,2,3,4,5,6 ,then definately 7 th number will be the one who has its one of pair in previous six where their sum is 11, random 6 number can be anyone from 1-10 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes Group the integers into a pair that add to 11 {(1,10),(5,6),(4,7),(3,8),(2,9)} Now applying pigeon hole we have to select 7 integers from 5 pairs there will be atleast 2 pairs that have both their elements in the 7 integers Sanket_ answered Aug 25, 2016 Sanket_ comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes I have shown the pairs that can form the sum of 11. Now, consider example. Lets say that I select 1,2,3,4,5. Now, I select 2 more elements. These 2 elements will form pairs with atleast 2 elements from first 5 elements selected previously. Hence, there are atleast 2 pairs that sum up to 11. Hence, the statement proved.(You can try out any 5 elements at first place. Next 2 elements will definitely map to 2 elements selected previously). Sushant Gokhale answered Aug 30, 2016 Sushant Gokhale comment Share Follow See all 2 Comments See all 2 2 Comments reply Vishal Goyal commented Sep 5, 2016 reply Follow Share Where did you apply pigeon hole principle 0 votes 0 votes Sushant Gokhale commented Sep 6, 2016 reply Follow Share @Vishal. Its not exactly pigeon hole but similar to that. 0 votes 0 votes Please log in or register to add a comment.