GMAT Question of the Day: Daily via email | Daily via Instagram New to GMAT Club? Watch this Video

 It is currently 07 Jul 2020, 21:01 ### GMAT Club Daily Prep

#### Thank you for using the timer - this advanced tool can estimate your performance and suggest more practice questions. We have subscribed you to Daily Prep Questions via email.

Customized
for You

we will pick new questions that match your level based on your Timer History

Track

every week, we’ll send you an estimated GMAT score based on your performance

Practice
Pays

we will pick new questions that match your level based on your Timer History

#### Not interested in getting valuable practice questions and articles delivered to your email? No problem, unsubscribe here.  # If a subset of integers is chosen from between 1 to 3000, inclusive

Author Message
TAGS:

### Hide Tags

Math Expert V
Joined: 02 Sep 2009
Posts: 65062
If a subset of integers is chosen from between 1 to 3000, inclusive  [#permalink]

### Show Tags 00:00

Difficulty:   55% (hard)

Question Stats: 38% (01:39) correct 63% (02:06) wrong based on 16 sessions

### HideShow timer Statistics

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

Are You Up For the Challenge: 700 Level Questions

_________________
Intern  B
Joined: 07 Jan 2018
Posts: 39
Re: If a subset of integers is chosen from between 1 to 3000, inclusive  [#permalink]

### Show Tags

1
1
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.
Manager  S
Joined: 05 Jan 2020
Posts: 114
Re: If a subset of integers is chosen from between 1 to 3000, inclusive  [#permalink]

### Show Tags

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
Target Test Prep Representative V
Status: Founder & CEO
Affiliations: Target Test Prep
Joined: 14 Oct 2015
Posts: 11047
Location: United States (CA)
Re: If a subset of integers is chosen from between 1 to 3000, inclusive  [#permalink]

### Show Tags

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.

_________________

# Scott Woodbury-Stewart

Founder and CEO

Scott@TargetTestPrep.com

See why Target Test Prep is the top rated GMAT quant course on GMAT Club. Read Our Reviews Re: If a subset of integers is chosen from between 1 to 3000, inclusive   [#permalink] 30 May 2020, 13:32

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