Let S=1,2,3,5,7,10,11.

Question

Let $S=\{1,2,3,5,7,10,11\}$. The number of nonempty subsets of $S$ that have the sum of all elements a multiple of 3, is \_\_\_\_\_\_\_.

Answer: 43

Accepted Answer

Classify elements by residue mod 3: residue $0$: $\{3\}$; residue $1$: $\{1,7,10\}$; residue $2$: $\{2,5,11\}$.

Counting subsets whose sum is $\equiv0\pmod3$ by size:

- 1 element: $S_1=1$ (just $\{3\}$)
- 2 elements: $S_2=\binom31\binom31=9$
- 3 elements: $S_3=\binom31\binom31\cdot1+1+1=11$
- 4 elements: $S_4=\binom33+\binom33+\binom32\binom32=11$
- 5 elements: $S_5=\binom32\binom32\times1=9$
- 6 elements: $S_6=1$
- 7 elements: $S_7=1$

$$\text{Total} = 1+9+11+11+9+1+1 = 43$$

Solutions · 1