What is the number of 7-element subsets of the set

[gmat_guy666]

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

OAC

[Ian Stewart]

If you subtract one multiple of 3 from another, you'll always get a multiple of 3.

The sum of the values in the set is 45, which is a multiple of 3. So if we remove two elements which sum to a multiple of 3, we'll get a 7-element subset which must sum to a multiple of 3.

So we really just want to count how many pairs of elements in the set add up to a multiple of 3. You can do that just by listing them all:

1, 2
1, 5
1, 8
2, 4
2, 7
3, 6
3, 9
4, 5
4, 8
5, 7
6, 9
7, 8

for 12 in total.

There's a faster way, but you'd need to know some remainder arithmetic - more than you'd ever need on the GMAT, so if this doesn't make sense, don't worry about it. But if we divide each element in our set by 3, we get each remainder (0, 1 and 2) equally often. So if we add two random values in the set and divide by 3, each of those remainders will be equally likely. In other words, 1/3 of the possible 2-element subsets we can pick will sum to a multiple of 3. Since there are 9C2 = 9*8/2! = 36 possible pairs of elements we can pick, and 1/3 of those pairs will sum to a multiple of 3, the answer is (1/3)(36) = 12.

[GMATGuruNY]

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

Sum of evenly spaced integers = (number on integers)(median).
In the set above:
Number of integers = 9.
Median = 5.
Thus:
Sum = 9*5 = 45.

The sum of the 9 integers is a MULTIPLE OF 3.
The sum of the 7-integer subset must also be a MULTIPLE OF 3.
Implication:
The sum of the two integers removed to yield the 7-element subset must also be A MULTIPLE OF 3.
The reason:
MULTIPLE OF 3 - MULTIPLE OF 3 = MULTIPLE OF 3.

Options for the two integers that are removed:
1, 2
1, 5
1, 8
2, 4
2, 7
3, 6
3, 9
4, 5
4, 8
5, 7
6, 9
7, 8.
Total options = 12.

The correct answer is C.