Let S=1,2,3,4,5,6,9.

Question

Let $S=\{1,2,3,4,5,6,9\}$. Then the number of elements in the set $T=\{A\subseteq S : A
e\emptyset 	ext{ and sum of elements of } A 	ext{ is not a multiple of } 3\}$ is:

Answer: 80

Accepted Answer

Classify by residue mod 3: residue 0: $\{3,6,9\}$ (3 elements); residue 1: $\{1,4\}$ wait recompute: $1\to1,4\to1,7\to1$ but 7 not in S; residue1: $\{1,4\}$ --- actually checking S again: $\{1,2,3,4,5,6,9\}$: $1\to1,2\to2,3\to0,4\to1,5\to2,6\to0,9\to0$. Residue0: $\{3,6,9\}$(3 elements); residue1: $\{1,4\}$(2 elements); residue2: $\{2,5\}$(2 elements).

Count subsets of each size NOT divisible by 3, summing across all subset sizes:

$$P=1: 4,\quad P=2: 14,\quad P=3: 22,\quad P=4: 22,\quad P=5: 14,\quad P=6: 4$$

$$\text{Total} = 4+14+22+22+14+4 = 80$$

Solutions · 1