AMC 12 Mock Exam 1 Problem 25

We must count subsets of $\{1,2,\dots,12\}$ (including the empty set) whose sum is divisible by $12$. Let $\varepsilon=e^{2\pi i/12}$ and $F(x)=\prod_{k=1}^{12}(1+x^k)$, whose coefficient of $x^s$ counts the subsets with sum $s$. The number of subsets with sum divisible by $12$ is $$N=\frac1{12}\sum_{j=0}^{11}F(\varepsilon^j).$$ Fix $j$ and let $m$ be the order of $\varepsilon^j$ (so $m\mid12$). As $k$ runs over $1,\dots,12$, $\varepsilon^{jk}$ runs over all $m$-th roots of unity, each exactly $\frac{12}m$ times. Since $\prod_{u^m=1}(x-u)=x^m-1$, setting $x=-1$ gives $\prod_{u^m=1}(1+u)=(-1)^m\left((-1)^m-1\right)$, which is $0$ if $m$ is even and $2$ if $m$ is odd. So $F(\varepsilon^j)=0$ when $m$ is even and $F(\varepsilon^j)=2^{12/m}$ when $m$ is odd.

The odd values of $m$ dividing $12$ are $m=1$ (only $j=0$) and $m=3$ (the two values $j=4,8$). Therefore $$N=\frac{1}{12}\left(2^{12}+2\cdot2^{4}\right)=\frac{4096+32}{12}=\boxed{344}.$$