Bunuel wrote:
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
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
_________________
★
★
★
★
★
214 REVIEWS
5-STARS RATED ONLINE GMAT QUANT SELF STUDY COURSE
NOW WITH GMAT VERBAL (BETA)
See why Target Test Prep is the top rated GMAT quant course on GMAT Club. Read Our Reviews