GMAT Question of the Day - Daily to your Mailbox; hard ones only

It is currently 17 Oct 2018, 03:25

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

What is the number of 7-element subsets of the set {1, 2, 3, 4, 5, 6,

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

Hide Tags

Manager
Manager
avatar
Joined: 31 Aug 2009
Posts: 53
What is the number of 7-element subsets of the set {1, 2, 3, 4, 5, 6,  [#permalink]

Show Tags

New post 15 Sep 2009, 00:18
3
23
00:00
A
B
C
D
E

Difficulty:

  95% (hard)

Question Stats:

47% (02:27) correct 53% (02:38) wrong based on 258 sessions

HideShow timer Statistics

What is the number of 7-element subsets of the set {1, 2, 3, 4, 5, 6, 7, 8, 9} for which the sum of those 7 elements is a multiple of 3 ?

(A) 10
(B) 11
(C) 12
(D) 13
(E) 14
Most Helpful Expert Reply
Veritas Prep GMAT Instructor
User avatar
P
Joined: 16 Oct 2010
Posts: 8386
Location: Pune, India
Re: What is the number of 7-element subsets of the set {1, 2, 3, 4, 5, 6,  [#permalink]

Show Tags

New post 02 Jan 2011, 10:56
1
6
nonameee wrote:
Can I ask someone to take a look at this one? The solution provided by manifestdestiny is a very good one. But I would like someone to explain me the method suggested by gmatcouple.

Also, I don't know how this could be proved:

Quote:
manifestdestiny: which is ONE THIRD OF THE TIME


Thank you.


gmatcouple solution:
{1, 2, 3, 4, 5, 6, 7, 8, 9} - Sum = 45 is Divisible by 3
Now, if the sum of 7 of these numbers has to be divisible by 3, the sum of the remaining 2 numbers should also be divisible by 3. [e.g. if I take out 1 and 2 from the 9 numbers, the sum of 1 and 2 is 3 (a multiple of 3). So the leftover sum of the 7 numbers will be 42 (another multiple of 3) (Which simply implies from the fact that when two multiples of 3 are added, we get another multiple of 3)]

Now, all positive integers are of one of 3 forms: (3n) or (3n + 1) or (3n + 2)... where n is a whole number... e.g. 9 is of the form 3n, 10 is of the form 3n+1, 11 is of the form 3n + 2, 12 is again of the form 3n and so on....

Of the 9 consecutive numbers above, 3 are of the form 3n, 3 are of the form (3n + 1) and 3 are of the form (3n + 2)
3n: 3, 6, 9
3n + 1: 1, 4, 7
3n + 2: 2, 5, 8

To choose 3 numbers from these 9 such that their sum is a multiple of 3, we can either take 2 numbers which are of the form 3n (e.g. 3 + 6) or we can take 1 number of the form (3n + 1) and one number of the form (3n + 2) (e.g. 1 and 2)

2 numbers of the form 3n: 3C2 = 3 ways
1 number of the form (3n + 1) and one number of the form (3n + 2): 3C1 * 3C1 = 9 ways
So there are a total of 12 ways of picking 2 numbers whose sum is a multiple of 3.
Or you could enumerate all of them which is tricky since you could make a mistake in counting.

manifestdestiny: which is ONE THIRD OF THE TIME

{1, 2, 3, 4, 5, 6, 7, 8, 9}
Take 2 numbers at a time:
1, 2 - Sum 3 (form 3n)
1, 3 - Sum 4 (form 3n + 1)
1, 4 - Sum 5 (form 3n + 2)
1, 5 - Sum 6 (form 3n)
1, 6 - Sum 7 (form 3n + 1) and so on
Since you can select 2 numbers in 9C2 = 36 ways, a third of them will have sum of the form 3n, a third will have the sum of the form (3n + 1) and a third will have the sum of the form (3n + 2).
Hence there are 12 ways of selecting 2 numbers such that their sum is of the form 3n

Note: This happens because the numbers are consecutive. It may not be true if the numbers are not consecutive.
e.g. If we have 3 numbers as given below:
1, 4, 5 and we pick 2 at a time: 1+4 = 5; 1+5 = 6; 4+5 = 9
Here, 2 of the 3 sums are divisible by 3
_________________

Karishma
Veritas Prep GMAT Instructor

Learn more about how Veritas Prep can help you achieve a great GMAT score by checking out their GMAT Prep Options >

GMAT self-study has never been more personalized or more fun. Try ORION Free!

Most Helpful Community Reply
Intern
Intern
avatar
Joined: 31 Aug 2009
Posts: 18
Re: What is the number of 7-element subsets of the set {1, 2, 3, 4, 5, 6,  [#permalink]

Show Tags

New post 21 Sep 2009, 15:34
20
7
there is actually a very quick way to answer this problem.

Remember, whenever you divide any number by 3, there are 3 possible remainders:
0, 1, or 2

Now let's figure out how many 7 digit subsets are possible from the original set. Using the combination formula, \(9C7\) we get 36. The only way that the sum of a subset will be divisible by 3 is if the remainder is 0, which is ONE THIRD OF THE TIME! So 1/3 of 36 = 12
General Discussion
Manager
Manager
avatar
Joined: 31 Aug 2009
Posts: 53
Re: What is the number of 7-element subsets of the set {1, 2, 3, 4, 5, 6,  [#permalink]

Show Tags

New post 15 Sep 2009, 00:22
i took the highest possible sum (which is 42) divided by 3 which is 14. That's the max set. then worked backward to see if i can make multiples of 3 from 1-14. Basically, can you make 42 out of those numbers? yes. can you make 39,(ie 3 less so take out 4 replace by 1.) ? i did it under 2-min. but not elegant at all. anybody have better solution?

a slightly quicker way was finding the max number you can making using all 7,6,5,4,3,2 etc.. and see how the delta between those sets behave.
Intern
Intern
avatar
Joined: 13 May 2008
Posts: 7
Re: What is the number of 7-element subsets of the set {1, 2, 3, 4, 5, 6,  [#permalink]

Show Tags

New post 15 Sep 2009, 00:45
The sum of all elements is 45 which is divisible by 3.

So the sum of any 7-element subset will be divisible by 3 only if the sum of the remaining 2 elements is divisible by 3 too.

There are 13 ways of choosing 2 elements from that set so that their sum is divisible by 3 (i guess there are not so many of them so i just list them all out). There might be another way to count them though.

So the answer is 13.
Manager
Manager
avatar
Joined: 28 Jul 2009
Posts: 114
Location: India
Schools: NUS, NTU, SMU, AGSM, Melbourne School of Business
Re: What is the number of 7-element subsets of the set {1, 2, 3, 4, 5, 6,  [#permalink]

Show Tags

New post 15 Sep 2009, 01:05
2
thailandvc wrote:
i took the highest possible sum (which is 42) divided by 3 which is 14. That's the max set. then worked backward to see if i can make multiples of 3 from 1-14. Basically, can you make 42 out of those numbers? yes. can you make 39,(ie 3 less so take out 4 replace by 1.) ? i did it under 2-min. but not elegant at all. anybody have better solution?

a slightly quicker way was finding the max number you can making using all 7,6,5,4,3,2 etc.. and see how the delta between those sets behave.


I am not sure of this but I figured it out the answer as 12.
Sum of elements = 45(9+8+...+1)
Removing 2 elements at a time :
45 - 1,2 = 42
45 - 1,5 = 39
45 - 1,8 = 36
45 - 2,4 = 39 (2,1 already appeared)
45 - 2,7 = 36

and so... I ended up getting on 12. What is the OA? And unfortunately no. This was not a 2 min solution for the first time. But this seemed a more organised way to approach. Hope I am right here. :)
_________________

GMAT offended me. Now, its my turn!
Will do anything for Kudos! Please feel free to give one. :)

Intern
Intern
avatar
Joined: 13 May 2008
Posts: 7
Re: What is the number of 7-element subsets of the set {1, 2, 3, 4, 5, 6,  [#permalink]

Show Tags

New post 15 Sep 2009, 01:37
oh yeah, there're only 12 pairs.. i counted wrongly.. wondering how many points would this simple mistake cost me in the real exam =(
Director
Director
avatar
Joined: 23 Apr 2010
Posts: 547
Re: What is the number of 7-element subsets of the set {1, 2, 3, 4, 5, 6,  [#permalink]

Show Tags

New post 02 Jan 2011, 07:42
Can I ask someone to take a look at this one? The solution provided by manifestdestiny is a very good one. But I would like someone to explain me the method suggested by gmatcouple.

Also, I don't know how this could be proved:

Quote:
manifestdestiny: which is ONE THIRD OF THE TIME


Thank you.
Director
Director
avatar
Joined: 23 Apr 2010
Posts: 547
Re: What is the number of 7-element subsets of the set {1, 2, 3, 4, 5, 6,  [#permalink]

Show Tags

New post 05 Jan 2011, 04:58
Karishma, thank you for your reply. I understand your explanation of gmatcouple's solution. However, I don't quite understand the explanation of manifestdestiny's solution. I can see that you use the same logic as in gmatcouple's solution.

Actually, I think both your explanations are pretty much the same: instead of counting 7-member subsets divisible by 3, we count 2-member subsets divisible by 3 (this can be done because there's a bijection between these subsets).
Veritas Prep GMAT Instructor
User avatar
P
Joined: 16 Oct 2010
Posts: 8386
Location: Pune, India
Re: What is the number of 7-element subsets of the set {1, 2, 3, 4, 5, 6,  [#permalink]

Show Tags

New post 05 Jan 2011, 06:04
nonameee wrote:
Karishma, thank you for your reply. I understand your explanation of gmatcouple's solution. However, I don't quite understand the explanation of manifestdestiny's solution. I can see that you use the same logic as in gmatcouple's solution.

Actually, I think both your explanations are pretty much the same: instead of counting 7-member subsets divisible by 3, we count 2-member subsets divisible by 3 (this can be done because there's a bijection between these subsets).


manifestdestiny says in his solution that remainder will be 0 in 1/3 of the 36 ways in which you can select 7 out of 9 digits.
Selecting 7 out of 9 is same as selecting 2 out of 9 and putting them away. You split the 9 into 2 groups - 7 digits and 2 digits. It doesnt matter which one you are analyzing since, as you said, there is a bijection between the two sets (each element of the two sets is a set). It is always easier to wrap your head around 2 digits than it is to do the same for 7 digits.
Remainder 0 is same as form 3n. I don't need to find remainders in every step to explain so I stick with the forms.
I have given you the pattern above to explain why a THIRD of them will be divisible by 3 (which is the concept manifestdestiny uses.) Conceptually, both have given the same solution. gmatcouple executes it, manifestdestiny arrives at the answer conceptually.
_________________

Karishma
Veritas Prep GMAT Instructor

Learn more about how Veritas Prep can help you achieve a great GMAT score by checking out their GMAT Prep Options >

GMAT self-study has never been more personalized or more fun. Try ORION Free!

Director
Director
avatar
Joined: 23 Apr 2010
Posts: 547
Re: What is the number of 7-element subsets of the set {1, 2, 3, 4, 5, 6,  [#permalink]

Show Tags

New post 05 Jan 2011, 06:10
Karishma, thanks a lot for your explanation. I just thought that manifestdestiny arrived at his solution through analyzing 7-number subsets rather than 2-number subsets.
Director
Director
User avatar
Joined: 07 Aug 2011
Posts: 540
Concentration: International Business, Technology
GMAT 1: 630 Q49 V27
GMAT ToolKit User
Re: What is the number of 7-element subsets of the set {1, 2, 3, 4, 5, 6,  [#permalink]

Show Tags

New post 02 Jan 2015, 09:59
1
VeritasPrepKarishma wrote:
nonameee wrote:
Can I ask someone to take a look at this one? The solution provided by manifestdestiny is a very good one. But I would like someone to explain me the method suggested by gmatcouple.

Also, I don't know how this could be proved:

Quote:
manifestdestiny: which is ONE THIRD OF THE TIME


Thank you.


gmatcouple solution:
{1, 2, 3, 4, 5, 6, 7, 8, 9} - Sum = 45 is Divisible by 3
Now, if the sum of 7 of these numbers has to be divisible by 3, the sum of the remaining 2 numbers should also be divisible by 3. [e.g. if I take out 1 and 2 from the 9 numbers, the sum of 1 and 2 is 3 (a multiple of 3). So the leftover sum of the 7 numbers will be 42 (another multiple of 3) (Which simply implies from the fact that when two multiples of 3 are added, we get another multiple of 3)]

Now, all positive integers are of one of 3 forms: (3n) or (3n + 1) or (3n + 2)... where n is a whole number... e.g. 9 is of the form 3n, 10 is of the form 3n+1, 11 is of the form 3n + 2, 12 is again of the form 3n and so on....

Of the 9 consecutive numbers above, 3 are of the form 3n, 3 are of the form (3n + 1) and 3 are of the form (3n + 2)
3n: 3, 6, 9
3n + 1: 1, 4, 7
3n + 2: 2, 5, 8

To choose 3 2 numbers from these 9 such that their sum is a multiple of 3, we can either take 2 numbers which are of the form 3n (e.g. 3 + 6) or we can take 1 number of the form (3n + 1) and one number of the form (3n + 2) (e.g. 1 and 2)

2 numbers of the form 3n: 3C2 = 3 ways
1 number of the form (3n + 1) and one number of the form (3n + 2): 3C1 * 3C1 = 9 ways
So there are a total of 12 ways of picking 2 numbers whose sum is a multiple of 3.
Or you could enumerate all of them which is tricky since you could make a mistake in counting.

manifestdestiny: which is ONE THIRD OF THE TIME

{1, 2, 3, 4, 5, 6, 7, 8, 9}
Take 2 numbers at a time:
1, 2 - Sum 3 (form 3n)
1, 3 - Sum 4 (form 3n + 1)
1, 4 - Sum 5 (form 3n + 2)
1, 5 - Sum 6 (form 3n)
1, 6 - Sum 7 (form 3n + 1) and so on
Since you can select 2 numbers in 9C2 = 36 ways, a third of them will have sum of the form 3n, a third will have the sum of the form (3n + 1) and a third will have the sum of the form (3n + 2).
Hence there are 12 ways of selecting 2 numbers such that their sum is of the form 3n

Note: This happens because the numbers are consecutive. It may not be true if the numbers are not consecutive.
e.g. If we have 3 numbers as given below:
1, 4, 5 and we pick 2 at a time: 1+4 = 5; 1+5 = 6; 4+5 = 9
Here, 2 of the 3 sums are divisible by 3

_________________

Thanks,
Lucky

_______________________________________________________
Kindly press the Image to appreciate my post !! :-)

Manager
Manager
avatar
Joined: 22 Aug 2014
Posts: 163
Re: What is the number of 7-element subsets of the set {1, 2, 3, 4, 5, 6,  [#permalink]

Show Tags

New post 31 Mar 2015, 09:00
1
what i understood from the question was that how many ways are possible that we choose 7 numbers from the set and the sum of those 7 numbers is multiple of 3?
This is what I did-

Max sum is 45 when we take 9 numbers,so we have to eliminate only 2 numbers such that sum of 7 numbers is multiple of 3.Now,max sum=45=15*3
so possible sums-42(3*14),39(13*3),36,33,30,27....


now to make 42 we have to eliminate 3(2,1)
To make 39,we have to eliminate 6(5,1)(4,2)
To make 36,we have to eliminate 9-(8,1) (7,2) (6,3) (4,5)
To make 33,we have to eliminate 12-(8,4) (7,5) (9,3)
To make 30 ,we have to eliminate 15-(8,7) (9,6)


thus,12 choices!
Manager
Manager
User avatar
S
Joined: 22 Jan 2014
Posts: 176
WE: Project Management (Computer Hardware)
Re: What is the number of 7-element subsets of the set {1, 2, 3, 4, 5, 6,  [#permalink]

Show Tags

New post 06 Apr 2015, 05:18
1
thailandvc wrote:
What is the number of 7-element subsets of the set {1, 2, 3, 4, 5, 6, 7, 8, 9} for which the sum of those 7 elements is a multiple of 3 ?

(A) 10
(B) 11
(C) 12
(D) 13
(E) 14


we have 3 elements each of 3k, 3k+1, and 3k+2 form

for 7 elements to form 3k, the following is possible:

1) 2*(3k+1) + 2*(3k+2) + 3*3k --> C(3,2)*C(3,2)*C(3,3) = 9
2) 3*(3k+1) + 3*(3k+2) + 1*3k --> C(3,3)*C(3,3)*C(3,1) = 3

total = 12.
_________________

Illegitimi non carborundum.

Intern
Intern
avatar
Joined: 06 Aug 2014
Posts: 9
Location: Russian Federation
Concentration: Technology, Strategy
GMAT 1: 690 Q49 V35
GPA: 3.88
WE: Engineering (Aerospace and Defense)
Re: What is the number of 7-element subsets of the set {1, 2, 3, 4, 5, 6,  [#permalink]

Show Tags

New post 08 Apr 2015, 06:54
Min sum of set elements: 1+2+3+4+5+6+7 = 28, max sum of set elements: 3+4+5+6+7+8+9 = 37. We have only 3 possible sums meeting requirements: 30 33 36. For each sum there are only for possible arrangements. So the total number of sets for which the sum of elements has to be divisible by 3 is 12.
Director
Director
User avatar
G
Joined: 23 Jan 2013
Posts: 575
Schools: Cambridge'16
What is the number of 7-element subsets of the set {1, 2, 3, 4, 5, 6,  [#permalink]

Show Tags

New post 09 Apr 2015, 02:47
1,2,3,4,5,6,7,8,9

we have 3 multiples (3,6,9) and 6 non-multiples (1,2,4,5,7,8).
All sums of 7 numbers to be multiple we should have three multiples and sum of 4 non-multiples to be multiple of 3

3C3*6C4=1*15=15

but 3 combinations of non-multiples do not give multiple of 3 in sum: 1,2,4,7 ; 1,2,5,8 ; 2,4,5,8

so, 15-3=12

C
Veritas Prep GMAT Instructor
User avatar
P
Joined: 16 Oct 2010
Posts: 8386
Location: Pune, India
Re: What is the number of 7-element subsets of the set {1, 2, 3, 4, 5, 6,  [#permalink]

Show Tags

New post 09 Apr 2015, 21:27
thailandvc wrote:
What is the number of 7-element subsets of the set {1, 2, 3, 4, 5, 6, 7, 8, 9} for which the sum of those 7 elements is a multiple of 3 ?

(A) 10
(B) 11
(C) 12
(D) 13
(E) 14

Quote:
Qu 1: had the question been sum to be divisible by 5 . in that case we could not use this trick. is there a variant of this technique to deal with such odd situation ?


The sum of all elements is 45.
If you want to remove two elements such that the sum stays a multiple of 5, the sum of the elements removed must be a multiple of 5. Say if you remove 10, you will be left with 35.
In how many ways can you make 5? 1+4, 2+3
In how many ways can you make 10? 1+9, 2+8, 3+7, 4+6
In how many ways can you make 15? 6+9, 7+8
You cannot make 20 and higher multiplies.

Total 8 ways

Quote:
Qu :2 : if we have to think on lines of unit digit , the unit digit of the sum of 7 numbers should be 0 or 5 . how should we go ahead with this method.

Explain how you intend to do it and I will tell you whether it is correct.
_________________

Karishma
Veritas Prep GMAT Instructor

Learn more about how Veritas Prep can help you achieve a great GMAT score by checking out their GMAT Prep Options >

GMAT self-study has never been more personalized or more fun. Try ORION Free!

Retired Moderator
avatar
B
Status: I Declare War!!!
Joined: 02 Apr 2014
Posts: 237
Location: United States
Concentration: Finance, Economics
GMAT Date: 03-18-2015
WE: Asset Management (Investment Banking)
GMAT ToolKit User Premium Member
What is the number of 7-element subsets of the set {1, 2, 3, 4, 5, 6,  [#permalink]

Show Tags

New post 08 Aug 2016, 17:43
Hi!
Bunuel , chetan4u , magoosh , kindly share your solution on this as I am sure it will another concept learning for people like me.
Thnks
Math Revolution GMAT Instructor
User avatar
V
Joined: 16 Aug 2015
Posts: 6375
GMAT 1: 760 Q51 V42
GPA: 3.82
Premium Member
Re: What is the number of 7-element subsets of the set {1, 2, 3, 4, 5, 6,  [#permalink]

Show Tags

New post 05 Sep 2017, 18:27
thailandvc wrote:
What is the number of 7-element subsets of the set {1, 2, 3, 4, 5, 6, 7, 8, 9} for which the sum of those 7 elements is a multiple of 3 ?

(A) 10
(B) 11
(C) 12
(D) 13
(E) 14



\(1, 4, 7\) : They have a remainder \(1\) when they are divided by \(3\).
\(2, 5, 8\) : They have a remainder \(2\) when they are divided by \(3\).
\(3, 6, 9\) : They are multiples of \(3\).

\(1 + 2 + 3 + ... + 9 = 45\). It is a multiple of \(3\).
We need to choose two numbers whose sum is a multiple of \(3\) and subtract their sum from \(45\).
There are two cases. One is choosing two numbers from \(\{ 3, 6, 9 \}\) and other case is choosing one number from \(\{ 1, 4, 7 \}\) and one number from \(\{ 2, 5, 8 \}\).
The number of ways to choose two numbers from \(\{ 3, 6, 9 \}\) is \({}_3C_2 = 3\). And the number of ways to choose one number from \(\{ 1, 4, 7 \}\) and one number from \(\{ 2, 5, 8 \}\) is \({}_3C_1 * {}_3C_1 = 3*3 = 9\).
The number of all cases is \(3 + 9 = 12\).

The answer is C.
_________________

MathRevolution: Finish GMAT Quant Section with 10 minutes to spare
The one-and-only World’s First Variable Approach for DS and IVY Approach for PS with ease, speed and accuracy.
"Only $99 for 3 month Online Course"
"Free Resources-30 day online access & Diagnostic Test"
"Unlimited Access to over 120 free video lessons - try it yourself"

Senior Manager
Senior Manager
avatar
G
Joined: 02 Apr 2014
Posts: 471
GMAT 1: 700 Q50 V34
Re: What is the number of 7-element subsets of the set {1, 2, 3, 4, 5, 6,  [#permalink]

Show Tags

New post 11 Mar 2018, 04:06
Set = {1,2,3,4,5,6,7,8,9}
Modulo by 3 = {1,2,0,1,2,0,1,2,0}

so if we remove {0,0} or {1,2} combos from the set, remaining set sum will be divisible by 3

selecting {0,0}, there are three numbers with modulo 0, => 3c2 = 3
selecting {1,2}, there are three numbers with modulo 1 and three numbers with modulo 2, 3C1 * 3C1 = 9

total {0,0} + {1,2} = 12
GMAT Club Bot
Re: What is the number of 7-element subsets of the set {1, 2, 3, 4, 5, 6, &nbs [#permalink] 11 Mar 2018, 04:06
Display posts from previous: Sort by

What is the number of 7-element subsets of the set {1, 2, 3, 4, 5, 6,

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


Copyright

GMAT Club MBA Forum Home| About| Terms and Conditions and Privacy Policy| GMAT Club Rules| Contact| Sitemap

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

Kindly note that the GMAT® test is a registered trademark of the Graduate Management Admission Council®, and this site has neither been reviewed nor endorsed by GMAC®.