Let S = 1, 2, 3, 4, 5, 6, 9. Then the number of elements in the set T = A ⊆ S : A ≠ φ and the sum of all the elements of A is not a multiple of 3 is _______________.

Solution

Maths sir · 4 steps

Sort the elements by remainder mod 3, count subsets whose sum is a multiple of 3, then subtract from 128.

1. Group by remainder. Divide each element by 3. Remainder 0: {3, 6, 9}. Remainder 1: {1, 4}. Remainder 2: {2, 5}. Only the remainders decide whether a sum is a multiple of 3.
2. When is it divisible. Say a subset takes i elements from {1, 4} and j from {2, 5}. Its sum leaves remainder i + 2j ≡ i - j (mod 3). Since i, j ≤ 2, the sum is a multiple of 3 only when i = j. The elements 3, 6 and 9 never change the remainder, so each one is free to be in or out: 2³ = 8 ways.

   i = j	Ways from {1, 4}	Ways from {2, 5}	Ways
   0	C(2, 0) = 1	C(2, 0) = 1	1
   1	C(2, 1) = 2	C(2, 1) = 2	4
   2	C(2, 2) = 1	C(2, 2) = 1	1

3. Multiples of 3. There are 1 + 4 + 1 = 6 choices from {1, 2, 4, 5}, and each pairs with 8 choices from {3, 6, 9}. So 6 × 8 = 48 subsets have a sum that is a multiple of 3. This count includes the empty set, whose sum is 0.
4. So. S has 2⁷ = 128 subsets, so 128 - 48 = 80 have a sum that is not a multiple of 3. The empty set is already among the 48 removed, so T has 80 elements.

The common slip: 79. Removing the empty set a second time gives 127 - 48 = 79, not 80. Its sum is 0, so it was already among the 48 multiples of 3.

The idea to keep. For subset-sum divisibility, work with remainders only. Elements divisible by the divisor never change the remainder, so each one just doubles the count.

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