
3. A finite non-empty set $S$ of integers is called 3 -good if the the sum of the elements of $S$ is divisble by 3 . Find the number of 3 -good non-empty subsets of $\{0,1,2, \ldots, 9\}$.


Solution. Let $A$ be a 3 -good subset of $\{0,1, \ldots, 9\}$. Let $A_{1}=A \cap\{0,3,6,9\}, A_{2}=A \cap\{1,4,7\}$ and $A_{3}=A \cap\{2,5,8\}$. Then there are three possibilities:

- $\left|A_{2}\right|=3,\left|A_{3}\right|=0$
- $\left|A_{2}\right|=0,\left|A_{3}\right|=3$
- $\left|A_{2}\right|=\left|A_{3}\right|$.

Note that there are 16 possibilities for $A_{1}$. Therefore the first two cases correspond to a total of 32 subsets that are 3 -good. The number of subsets in the last case is $16\left(1^{2}+3^{2}+3^{2}+1^{2}\right)=320$. Note that this also includes the empty set. Therefore there are a total of 351 non-empty 3good subsets of $\{0,1,2, \ldots, 9\}$.
