Question

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 _________. 
 

Hint:

For counting problems involving sums modulo n, the roots of unity method is very powerful. The number of subsets of a set S whose sum is divisible by n is given by \(\frac{1}{n} \sum_{j=0}^{n-1} \prod_{s \in S} (1 + \omega_j^s)\), where \(\omega_j\) are the n-th roots of unity.

Answer 1

Correct Answer: 80

Step 1: Classify the elements of S based on their remainder modulo 3. 
This helps in analyzing the sum of elements in any subset. - Set of elements with remainder 0 mod 3: \(S_0 = \{3, 6, 9\}\). Number of elements \(n_0 = 3\). - Set of elements with remainder 1 mod 3: \(S_1 = \{1, 4\}\). Number of elements \(n_1 = 2\). - Set of elements with remainder 2 mod 3: \(S_2 = \{2, 5\}\). Number of elements \(n_2 = 2\). 
Step 2: Use a generating function (polynomial) approach. 
Let \(\omega = e^{i2\pi/3}\) be a complex cube root of unity. We know \(1+\omega+\omega^2=0\). Consider the product: \[ P(x) = \prod_{k \in S} (1 + x^k) \] The total number of subsets (including the empty set) whose sum is a multiple of 3 is given by \(\frac{1}{3}(P(1) + P(\omega) + P(\omega^2))\). |
Step 3: Evaluate P(1), P(\(\omega\)), and P(\(\omega^2\)). 
- \(P(1) = \prod_{k \in S} (1+1) = 2^{|S|} = 2^7 = 128\). This is the total number of subsets.
- \(P(\omega) = \prod_{k \in S} (1+\omega^k)\). We group terms based on their class mod 3.
- For \(k \in S_0\), \(k=3m\), so \(\omega^k = (\omega^3)^m 
= 1^m = 1\). The product is \((1+1)(1+1)(1+1) = 2^3\).
- For \(k \in S_1\), \(k=3m+1\), so \(\omega^k = \omega\).
The product is \((1+\omega)(1+\omega) = (1+\omega)^2\).
- For \(k \in S_2\), \(k=3m+2\), so \(\omega^k = \omega^2\).
The product is \((1+\omega^2)(1+\omega^2) = (1+\omega^2)^2\).
\[ P(\omega) = 2^3 (1+\omega)^2 (1+\omega^2)^2 = 8 (-\omega^2)^2 (-\omega)^2 = 8 (\omega^4)(\omega^2) = 8\omega^6 = 8(1) = 8 \] - \(P(\omega^2)\) will be the complex conjugate of \(P(\omega)\), which is also 8. Or we can calculate it:
\[ P(\omega^2) = 2^3 (1+\omega^2)^2 (1+\omega^4)^2 = 8 (-\omega)^2 (1+\omega)^2 = 8 \omega^2 (-\omega^2)^2 = 8\omega^2 \omega^4 = 8\omega^6 = 8 \] Step 4: Calculate the number of subsets with sum divisible by 3. 
Let \(N_0\) be the number of subsets (including \(\emptyset\)) whose sum is a multiple of 3.
\[ N_0 = \frac{1}{3}(128 + 8 + 8) = \frac{144}{3} = 48 \] This count includes the empty set (whose sum is 0). The number of non-empty subsets with sum divisible by 3 is \(48 - 1 = 47\).
Step 5: Calculate the final answer. 
The total number of non-empty subsets of S is \(2^7 - 1 = 127\).
The number of subsets in T is the total number of non-empty subsets minus the number of non-empty subsets whose sum is a multiple of 3.
\[ |T| = 127 - 47 = 80 \]