Problem
COM-B2-M09-P019 Subset Sum Modulo 3
Let \(m\ge 1\). Prove that the number of subsets of \(\{1,2,\ldots,3m\}\) whose sum of elements is divisible by \(3\) equals
\[\frac{2^{3m}+2^{m+1}}{3}.\]
Use the generating function \(F(t)=\prod_{j=1}^{3m}(1+t^j)\) and substitute the roots of \(z^3=1\).
Let \(\omega\ne 1\) be a cube root of unity, so \(1+\omega+\omega^2=0\). If \(F(t)=\prod_{j=1}^{3m}(1+t^j)\), then the number of coefficients whose degree is divisible by \(3\) is
\[\frac{F(1)+F(\omega)+F(\omega^2)}{3}.\]
We have \(F(1)=2^{3m}\). Among the numbers \(1,\ldots,3m\), each residue \(0,1,2\) modulo \(3\) appears \(m\) times. Hence
\[F(\omega)=(1+1)^m(1+\omega)^m(1+\omega^2)^m=2^m((1+\omega)(1+\omega^2))^m.\]
But \((1+\omega)(1+\omega^2)=1+\omega+\omega^2+\omega^3=1\), so \(F(\omega)=2^m\). Similarly \(F(\omega^2)=2^m\). Thus the answer is \(\frac{2^{3m}+2^m+2^m}{3}=\frac{2^{3m}+2^{m+1}}{3}\).
This is an olympiad-level residue filter; it should come after the parity filter.