BREAKING: Target Test Prep releases Brand New 2026 On Demand GMAT prep course

Redeem

Sub-setting

This topic has expert replies
Post new topic Post Reply
Previous Topic Next Topic
Master | Next Rank: 500 Posts
Posts: 487
Joined: Fri Mar 27, 2009 5:49 am
Thanked: 36 times

Sub-setting

by dtweah » Tue May 19, 2009 12:18 pm
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
Top
Source: — Data Sufficiency |
Junior | Next Rank: 30 Posts
Posts: 26
Joined: Thu Dec 11, 2008 12:02 am
Thanked: 1 times

by francopiccolo » Tue May 19, 2009 5:16 pm
This took me long, I hope someone knows a faster approach.

We know that 3, 6 and 9 are multiples of 3.

We know that the remainders of dividing these numbers by 3 are::

1 = 2, 2 = 1, 4 = 1, 5 = 2, 7 = 1, 8 = 2.

To have numbers which sum a multiple of 3, each number with remainder 1 must be accompanied by a number with remainder 2, or by 2 numbers with remainder 1.

So we have the following cases:

(i) 3 numbers with remainder 1, 3 numbers with remainder 2 and one of the multiples. Ex: 2,4,7 + 1,5,8 + 3
(i) Two pairs of a number with remainder 1 and a number with remainder 2 accompannied by the 3 multiples. Ex: 1,2 + 4,5 + 3,6,9
(iii) 3 pairs of a number with remainder 1 and a number with remainder 2.
Ex: 1,2 + 4,5 + 7,8.

For (i) we have 3C1 possibilites = 3

For (ii) we have 4C2 * 4C2 possibilities = 3*3 = 9

For (iii) we have 1 possibility.

The number of possible subsets is 13.
Top
Post new topic Post Reply
• Page 1 of 1