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 _________.
Show 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.
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 \]
