Sub-setting

[dtweah]

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

[francopiccolo]

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.