retagged by
2,141 views
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?
retagged by

2 Answers

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
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).

Related questions

0 votes
0 votes
1 answer
1
aditi19 asked Oct 25, 2018
947 views
How many cards must be chosen from a standard deck of 52 cards to guarantee that there are at least two cards of each of two different kinds?what this question means?
1 votes
1 votes
1 answer
2
Sammohan Ganguly asked May 25, 2018
1,346 views
Suppose a graph $G$ has $6$ nodes. Prove that either $G$ or $G'$ must contain a triangle.($G'$ is the complement of $G$.) Prove it using pigeonhole principle.
8 votes
8 votes
1 answer
3
Anu asked Jul 14, 2015
13,333 views
During a month with 30 days, a baseball team plays at least one game a day, but no more than 45 games. Show that there must be a period of some number of consecutive days...
0 votes
0 votes
0 answers
4
Harish Karnam asked Aug 31, 2017
1,114 views
During a month with 30 days, a baseball team plays at least one game a day, but no morethan 45 games. Show that there must be a period of some number of consecutive days ...