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

Question

How many distinct integers from the set     must be chosen to guarantee that two of them have a sum of 25?

(A) 12
(B) 13
(C) 14
(D) 15
(E) 16

nick1816 · Answer

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.

tanpopo145 · Answer

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?

nick1816 · Answer

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

Shrey08 · Answer

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?

GMATinsight · Answer

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

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

Now, look at it this way
- If we choose {1, 2, 3, 4} the sum can NOT be 25
- If we choose half of the 16 numbers (one of each pair that makes sum = 25) even then no two terms will add up to 25
- therefore even after choosing 4+8 = 12 terms the sum is not becoming 25
- But if we choose one more term from remaining 8 numbers then the chosen number will definitely make a pair with another previously chosen number to give sum = 25

i.e. total Numbers needed to choose to ensure that sum 25 is 4+8+1 = 13 numbers

ShreyKapil08

yashikaaggarwal · Answer

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

Posted from my mobile device

nick1816 · Answer

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.

Kunni · Answer

Hi  VeritasKarishma

Could you please help?

Regards
Kunal

KarishmaB · Answer

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

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.

bumpbot · Answer

Automated notice from GMAT Club BumpBot: 

A member just gave Kudos to this thread, showing it’s still useful. I’ve bumped it to the top so more people can benefit. Feel free to add your own questions or solutions.

 This post was generated automatically.

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

Prep Toolkit

Top 5 GMAT Debrief Videos

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

My Rewards

GMAT Problem Solving (PS) Questions

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

Prep Toolkit

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

My Rewards