Let S = {1, 2, 3, 5, 7, 10, 11}. The number of non-empty subsets of S that have the sum of all elements a multiple of 3, is _____________.

Solution

Maths sir · 4 steps

Do not add up subsets one by one. Sort the numbers by remainder on division by 3 and count by remainders.

1. Sort by remainder. Divide each element by 3. Remainder 0: {3}. Remainder 1: {1, 7, 10}. Remainder 2: {2, 5, 11}.
2. Condition on counts. Say a subset takes a numbers from the remainder-1 group and b from the remainder-2 group. Its sum leaves remainder a + 2b, which is the same as a - b modulo 3. So the sum is a multiple of 3 exactly when a - b is a multiple of 3, with a, b each from 0 to 3.

   a (from {1,7,10})	b (from {2,5,11})	Ways
   0	0	1 × 1 = 1
   1	1	3 × 3 = 9
   2	2	3 × 3 = 9
   3	3	1 × 1 = 1
   3	0	1 × 1 = 1
   0	3	1 × 1 = 1

3. Add the element 3. The six cases give 1 + 9 + 9 + 1 + 1 + 1 = 22 choices. The element 3 does not change the remainder, so it can be in or out. That doubles the count to 22 × 2 = 44.
4. So. The count of 44 includes the empty set, whose sum 0 is a multiple of 3. Removing it leaves 43 non-empty subsets.

The common slip: 44. Forgetting to remove the empty set gives 44, not 43. Its sum is 0, so it passes the test but is not allowed.

The idea to keep. For divisibility of a sum by k, only remainders mod k matter. Group the elements by remainder, count by how many you take from each group, and remember the cases like (3, 0) where the counts differ by k.

Answer from the NTA final answer key. Solution by PrepWiser.