in Combinatory retagged by
2,133 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?
in Combinatory retagged by
by
2.1k views

1 comment

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
0

2 Answers

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

2 Comments

Where did you apply pigeon hole principle
0
0
@Vishal. Its not exactly pigeon hole but similar to that.
0
0

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true