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

Question

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

manifestdestiny · Accepted Answer

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

KarishmaB · Answer

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.

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

thailandvc · Answer

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.

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.

gmatcouple · Answer

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.

bhanushalinikhil · Answer

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.

gmatcouple · Answer

oh yeah, there're only 12 pairs.. i counted wrongly.. wondering how many points would this simple mistake cost me in the real exam =(

nonameee · Answer

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:

Thank you.

nonameee · Answer

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).

KarishmaB · Answer

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.

nonameee · Answer

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.

Lucky2783 · Answer

ssriva2 · Answer

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!

thefibonacci · Answer

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.

dmitry.n.lobanov · Answer

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.

Temurkhon · Answer

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

KarishmaB · Answer

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

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

Celestial09 · Answer

Hi! 
Bunuel , chetan4u , magoosh , kindly share your solution on this as I am sure it will another concept learning for people like me. 
Thnks

MathRevolution · Answer

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.

hellosanthosh2k2 · Answer

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

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

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

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

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