igate test series

Question

Selection of how many integers from the first ten positive integers (1, 2, ...) guarantees that there must be a pair of these integers with a sum equal to 11 ?

Comments

my appr.

Possible(x, y)solutions : (1, 10), (2, 9), (3, 8), (4, 7), (5, 6) so total 5 solution  where i am wrong?

---

In the worst case, we can select $5$ numbers such that sum of any pair of numbers is not equal to $11$, and selecting one more number will guarantee that sum of some pair of numbers is equal to $11$.

$\therefore answer = 6$.

---

@shishir__roy  can you give any example?

---

It's simply pigeon hole principle

If u choose randomly any 5 numbers and add 1 then surely there will be a pair whose sum will be 11

i.e.

1,2,3,4,5,6

there is (5,6)

So ans will be 6

Answer 1

Among numbers 1 to 10, there are 5 pairs that corresponds to the sum 11. They are (10,1),(9,2),(8,3),(7,4) and (6,5). We can create a run of selections without any pair corresponding to the sum 11 upto a max of 5 numbers. For eg. the set {1,2,3,4,5} does not have any pairs summing up as 11. But in this set, if we add another  number from the set {1,..10} – {1,2,3,4,5}, then there will be a pair which corresponds to the sum 11 and that will be the one that we have enumerated in the beginning. This problem corresponds to a pigeon hole principle where 5 holes are filled up without a matching sum;however, the 6th number have to be placed along with the pair that corresponds to the sum 11.