How many distinct integers from the set [1,2,3,..20] must be chosen to

x+y=25, where x<y and x and y are both positive integers

Minimum value y can take is 13.

Hence, we need to choose at least 13 distinct integers from the set to guarantee that two of them have a sum of 25.

I am quite confused. Could you please help to elaborate more?

I have these sets: 20+5,19+6,18+7,17+8,16+9,15+10,14+11,13+12 --> total 16 distinct integers?

This question is based on Pigeonhole principle. If you put n+1 items in n containers, then at least one container have more than 1 item(Simple right)

If you want to choose a set in which sum of two of numbers is equal to 25, then you must include at least one pair (you mentioned 8 of those)in your set. So you have to choose 9 out of these 16 numbers in order to guarantee that at least one of the 8 pairs must have chosen.

Total minimum integers you gotta choose = 9+4(remaining ones 1,2,3 and 4) = 13

Hello,

Why are we considering (1,2,3, and 4) when these numbers will never, along with any other integer in the set, yield a sum 25?
_________________

The set of numbers available is {1, 2, ...., 20}

i.e. Biggest number in the set is 20

which requires 5 to make sum = 25 [20+5 = 25]

therefore {1, 2, 3, 4} can NOT pair with any other number in set to make the sum = 25





ShreyKapil08

[quote="nick1816"]This question is based on Pigeonhole principle. If you put n+1 items in n containers, then at least one container have more than 1 item(Simple right)

If you want to choose a set in which sum of two of numbers is equal to 25, then you must include at least one pair (you mentioned 8 of those)in your set. So you have to choose 9 out of these 16 numbers in order to guarantee that at least one of the 8 pairs must have chosen.

Total minimum integers you gotta choose = 9+4(remaining ones 1,2,3 and 4) = 13




[quote="tanpopo145"]I am quite confused. Could you please help to elaborate more?

I have these sets: 20+5,19+6,18+7,17+8,16+9,15+10,14+11,13+12 --> total 16 distinct integers?[/quote][/quote]

Could you briefly explain what's this pigeon hole principle. Moreover why you took 1 to 4 digits as distinct factors of Y. When they don't form 25 with the highest value given in set

[size=80][b][i]Posted from my mobile device[/i][/b][/size]
_________________

yashikaaggarwal ShreyKapil08

Let's change this question to ' How many maximum numbers we can choose from the set, so that sum of any 2 numbers is not equal to 25.

We will take the worst possible scenario, since we have to maximize the numbers in subset. Choose 1, 2, 3, 4 and one number out of each of the 8 pairs whose sum is equal to 25. In this scenario, sum of any 2 numbers can never be equal to 25.

One of such possible case-

S = {1,2,3,4,5,6,7,8,9,10,11,12}

20+5,19+6,18+7,17+8,16+9,15+10,14+11,13+12. I choose the highlighted one in my subset.

But now if i add any of the remaining 8 numbers in my subset, sum of 1 pair must be equal to 25. For Example if i add 13 in subset S , then 12+13 =25 or if i add 14, then 11+14=25 and so on.

Hence, by choosing (12+1) 13 numbers, we can guarantee that sum of at least 1 pair among chosen number is equal to 25.

Hi VeritasKarishma

Could you please help?

Regards
Kunal

How can we get a sum of 25 using 2 numbers from the given set?

[1, 2, 3, 4, 5, 6, 7, ... 17, 18, 19, 20]

1 + 24 (not in set) so not possible
...
5 + 20 (the first possible pair)
6 + 19
...

12 + 13 (last possible pair without repeating)

So how many maximum numbers can I pick such that NO two of them will add to give me 25?
I can pick all numbers from 1 to 12 and still no two of them will add to give me 25. The greatest numbers are 11 and 12 which will add to give 23.

But the moment I pick one more number (any one), I will get a pair that will give be 25.
Say I pick 13, now 12 + 13 = 25.
Say I pick 15, now 10 + 15 = 25
and so on...

So if I pick 13 numbers there will always be a pair that will add to give me 25.

Answer (B)

Note: The question should mention "how many minimum numbers must we pick ..." because if we pick all 20 numbers then also we will have pairs that will give us 25.

Hello from the GMAT Club BumpBot!

Thanks to another GMAT Club member, I have just discovered this valuable topic, yet it had no discussion for over a year. I am now bumping it up - doing my job. I think you may find it valuable (esp those replies with Kudos).

Want to see all other topics I dig out? Follow me (click follow button on profile). You will receive a summary of all topics I bump in your profile area as well as via email.
_________________