If a subset of integers is chosen from between 1 to 3000, inclusive

Question

If a subset of integers is chosen from between 1 to 3000, inclusive, such that no two integers add up to a multiple of nine, then what can be the maximum number of elements in the subset? Include both 1 and 3000?

(A) 1332
(B) 1333
(C) 1336
(D) 1668
(E) 1672

(A) 1332
(B) 1333
(C) 1336
(D) 1668
(E) 1672

Are You Up For the Challenge: 700 Level Questions

bidskamikaze · Accepted Answer

IMO C.

Let's see what integers can be included in the set:
1, 2,3,4, ( 5,6,7,8,9 ,10,11,12,13, 14,15,16,17,18 …..
Notice that thee underlined numbers cannot be included since the sum of any one of these underlined numbers and a particular non-underlined number will result in a multiple of 9.
So, after every 4 numbers the next 5 numbers cannot be considered. This cycle of 4 possible and next 5 not possible integers continues 333 times (till 2997).
The next three numbers 2998, 2999 and 3000 can also be included in the set.
We get a total of (333 X 4) + 3 = 1335 numbers.
Now, notice that number 9 can also be included in this set (since 9 plus any other number from this set will not be a multiple of 9).
Therefore, 1335+1 = 1336 numbers.
Answer C.

Lipun · Answer

The sum of the two integers can't be a multiple of 9.
Sum pairs of 9: (0,9) , (1,8) , (2,7) , (3,6) , (4,5)

From the above we understand that for:
(0,9) - if we take a multiple of 9, we can't take any other multiple of 9. This pair gives us 1 number (it can be any multiple of 9). Count = 1
(1,8) - if we take a number such that the remainder is 1 when divided by 9, then we need to discard all those numbers which leave a remainder of 8. Count = 334

Similarly,
(2,7) Count = 334
(3,6) Count = 334
(4,5) Count = 333, since the 334th occurrence will be 3001 (which is >3000).

Total = 1+333 + 334*3 = 334*4 = 1336

ScottTargetTestPrep · Answer

We can divide the integers from 1 to 3000, inclusive, into 9 groups:

Group 1: Those numbers that have a remainder of 1 when divided by 9, e.g., 1, 10, 19, etc.

Group 2: Those numbers that have a remainder of 2 when divided by 9, e.g., 2, 11, 20, etc.

Group 3: Those numbers that have a remainder of 3 when divided by 9, e.g., 3, 12, 21, etc.

Group 4: Those numbers that have a remainder of 4 when divided by 9, e.g., 4, 13, 22, etc.

Group 5: Those numbers that have a remainder of 5 when divided by 9, e.g., 5, 14, 23, etc.

Group 6: Those numbers that have a remainder of 6 when divided by 9, e.g., 6, 15, 24, etc.

Group 7: Those numbers that have a remainder of 7 when divided by 9, e.g., 7, 16, 25, etc.

Group 8: Those numbers that have a remainder of 8 when divided by 9, e.g., 8, 17, 26, etc.

Group 9: Those numbers that have a remainder of 0 when divided by 9, e.g., 9, 18, 27, etc.

Notice that if we pick a number in group 1, we can’t pick any number in group 8, since the sum of two numbers (one from each of these two groups) will be a multiple of 9 (for example, 1 + 17 = 18 is a multiple of 9). Likewise, if we pick a number in group 2, 3, or 4, we can’t pick any number in group 7, 6, or 5, respectively. Therefore, the best strategy in selecting elements for this subset we have is to pick all the numbers in certain groups and don’t pick any numbers in their “counter” groups.

Since 3000/9 = 333 R 3, the number of elements in each of the first three groups is 334 and that in each of the latter six groups is 333 (notice that 334 x 3 + 333 x 6 = 1002 + 1998 = 3000). Therefore, to maximize the number of elements in our subset, we should pick groups 1, 2 and 3 (since they have 1 more element than any of the other 6 groups) and pick either group 4 or 5 (but not both). This gives us a total of 334 x 3 + 333 = 1002 + 333 = 1335 elements for our subset.

Notice that we haven’t mentioned anything about what we should do with group 9. That is because all the numbers in group 9 are multiples of 9. We can pick just 1 element from this group since it won’t add up to a multiple of 9 with any of the other 1335 elements that are in our subset already (notice that it is a multiple of 9 but any of the other 1335 elements are not). However, we can’t pick another element from group 9; otherwise we will have 2 multiples of 9 and their sum will be a multiple of 9 also. Therefore, the maximum number of elements for our subset is 1335 + 1 = 1336.

Answer: C

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.

If a subset of integers is chosen from between 1 to 3000, inclusive

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

If a subset of integers is chosen from between 1 to 3000, inclusive

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