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

It is currently 12 Jul 2020, 12:00

Close

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
Your Progress

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.

Close

Request Expert Reply

Confirm Cancel

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

  new topic post reply Question banks Downloads My Bookmarks Reviews Important topics  
Author Message
TAGS:

Hide Tags

Find Similar Topics 
Math Expert
User avatar
V
Joined: 02 Sep 2009
Posts: 65194
If a subset of integers is chosen from between 1 to 3000, inclusive  [#permalink]

Show Tags

New post 26 May 2020, 07:56
00:00
A
B
C
D
E

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
Intern
User avatar
S
Joined: 07 Jan 2018
Posts: 47
GMAT ToolKit User CAT Tests
Re: If a subset of integers is chosen from between 1 to 3000, inclusive  [#permalink]

Show Tags

New post 26 May 2020, 09:26
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.
Answer C.
Manager
Manager
avatar
S
Joined: 05 Jan 2020
Posts: 129
Re: If a subset of integers is chosen from between 1 to 3000, inclusive  [#permalink]

Show Tags

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

Show Tags

New post 30 May 2020, 13:32
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
_________________

Scott Woodbury-Stewart

Founder and CEO

Scott@TargetTestPrep.com

  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

GMAT Club Bot
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

  new topic post reply Question banks Downloads My Bookmarks Reviews Important topics  





Powered by phpBB © phpBB Group | Emoji artwork provided by EmojiOne