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