© All Rights reserved @ LearnWithDash
Step-by-Step Solution
Step 1: Identify the Elements of S by Their Remainder Modulo 3
We have the set
S = \{1, 2, 3, 4, 5, 6, 9\}.
Classify these elements based on their remainder when divided by 3:
Elements that are multiples of 3 (remainder 0): 3, 6, 9 .
Elements that leave remainder 1 when divided by 3: 1, 4 .
Elements that leave remainder 2 when divided by 3: 2, 5 .
Step 2: Count All Possible Subsets
The total number of subsets of a set of 7 elements is
2^7 = 128.
Among these, one subset is the empty set \varnothing . Since we only want non-empty subsets, there are
128 - 1 = 127
non-empty subsets in total.
Step 3: Use Generating Functions to Track Sums Modulo 3
To count how many of these 127 non-empty subsets have a sum that is not a multiple of 3, we employ a generating-function-like reasoning:
Elements with remainder 0 (3, 6, 9): Each such element contributes (1 + x^0) because including or excluding it does not change the sum modulo 3. Combined, these three elements contribute
(1 + x^0)^3 = (1 + 1)^3 = 2^3 = 8.
Elements with remainder 1 (1, 4): Each such element contributes (1 + x^1) . Combined, these two elements give
(1 + x)(1 + x) = 1 + 2x + x^2.
Elements with remainder 2 (2, 5): Each such element contributes (1 + x^2) . Combined, these two elements give
(1 + x^2)(1 + x^2) = 1 + 2x^2 + x^4.
But since we work modulo 3 for the exponent, x^3 = 1 , so x^4 = x , giving
1 + 2x^2 + x.
Next, multiply the contributions from remainder 1 and remainder 2 groups:
(1 + 2x + x^2) \times (1 + 2x^2 + x).
Carrying out the multiplication carefully (and again noting x^3 = 1 ):
(1) \cdot (1 + 2x^2 + x) = 1 + 2x^2 + x.
(2x) \cdot (1 + 2x^2 + x) = 2x + 4x^3 + 2x^2 = 2x + 4(1) + 2x^2 = 2x + 4 + 2x^2.
(x^2) \cdot (1 + 2x^2 + x) = x^2 + 2x^4 + x^3 = x^2 + 2x + 1.
Summing these results:
(1 + 2x^2 + x) \;+\; (2x + 4 + 2x^2) \;+\; (x^2 + 2x + 1)
Collect like terms:
Constant terms: 1 + 4 + 1 = 6
x terms: x + 2x + 2x = 5x
x^2 terms: 2x^2 + 2x^2 + x^2 = 5x^2
Hence the product is:
6 + 5x + 5x^2.
Finally, include the effect of the three elements that are 0 \pmod{3} (which contributed a factor 8 ):
8 \times (6 + 5x + 5x^2) = 48 + 40x + 40x^2.
Step 4: Interpret the Coefficients and Exclude the Empty Subset
The coefficients in 48 + 40x + 40x^2 represent the number of subsets whose sum is respectively 0, 1, or 2 \; (\bmod \; 3) . Specifically:
Subsets with sum \equiv 0 \pmod{3} : 48
Subsets with sum \equiv 1 \pmod{3} : 40
Subsets with sum \equiv 2 \pmod{3} : 40
Among these 48 subsets that sum to 0 \pmod{3} , one is the empty subset. We only want non-empty subsets, so the count of non-empty subsets with sum 0 \pmod{3} is 48 - 1 = 47.
Thus, the total non-empty subsets is:
47 + 40 + 40 = 127.
Step 5: Final Count of Subsets Whose Sum is Not a Multiple of 3
We want the number of non-empty subsets whose sum is not divisible by 3, i.e., sum \equiv 1 or \equiv 2 \; (\bmod \; 3) :
40 + 40 = 80.
Therefore, the required number of subsets is 80.
