Let $S = \{1, 2, 3, 4, 5, 6, 9\}$. Then the number of elements in the set $T = \{A \subseteq S : A \neq…
Let $S = \{1, 2, 3, 4, 5, 6, 9\}$. Then the number of elements in the set $T = \{A \subseteq S : A \neq \emptyset\}$ and the sum of all the elements of $A$ is not a multiple of $3\}$ is
Solution
We can categorise the numbers of set $S = \{3n, 3(n-1), 3(n-2)\}$ where $n \in \{3, 6, 9\}$.
Let $N_p$ be the number of subsets of $S$ containing $p$ elements which are not divisible by 3.
For $p=1$, $n(N_1) = C_1^2 + C_1^2 = 4$.
For $p=2$, $n(N_2) = C_1^3 C_1^2 + C_1^3 C_1^2 + C_2^2 + C_2^2 = 14$.
For $p=3$, $n(N_3) = C_1^3 (C_2^2 + C_2^2) + C_2^3 (C_1^2 + C_1^2) + C_2^2 C_1^2 + C_1^2 C_2^2 = 22$.
For $p=4$, $n(N_4) = C_1^3 [(C_2^2 C_1^2) + (C_1^2 C_2^2)] + C_2^3 (C_2^2 + C_2^2) + C_3^3 (C_1^2 + C_1^2) = 22$.
For $p=5$, $n(N_5) = C_2^3 [(C_2^2 C_1^2) + (C_2^2 C_2^2)] + C_3^3 (C_2^2 + C_2^2) = 14$.
For $p=6$, $n(N_6) = [C_3^3 (C_2^2 C_1^2) + (C_1^2 C_2^2)] = 4$.
Therefore, the total subsets satisfying the given condition $= 4 + 14 + 22 + 22 + 14 + 4 = 80$.