Задача
COM-B2-M09-P019 Сумма подмножества по модулю 3
Пусть \(m\ge 1\). Докажите, что число подмножеств множества \(\{1,2,\ldots,3m\}\), сумма элементов которых делится на \(3\), равно
\[\frac{2^{3m}+2^{m+1}}{3}.\]
Используйте производящую функцию \(F(t)=\prod_{j=1}^{3m}(1+t^j)\) и подставьте корни уравнения \(z^3=1\).
Пусть \(\omega\ne 1\) - кубический корень из единицы, так что \(1+\omega+\omega^2=0\). Если \(F(t)=\prod_{j=1}^{3m}(1+t^j)\), то число коэффициентов со степенью, делящейся на \(3\), равно
\[\frac{F(1)+F(\omega)+F(\omega^2)}{3}.\]
Имеем \(F(1)=2^{3m}\). Среди чисел \(1,\ldots,3m\) по \(m\) чисел каждого остатка \(0,1,2\) по модулю \(3\). Поэтому
\[F(\omega)=(1+1)^m(1+\omega)^m(1+\omega^2)^m=2^m((1+\omega)(1+\omega^2))^m.\]
Но \((1+\omega)(1+\omega^2)=1+\omega+\omega^2+\omega^3=1\), значит, \(F(\omega)=2^m\). Аналогично \(F(\omega^2)=2^m\). Получаем \(\frac{2^{3m}+2^m+2^m}{3}=\frac{2^{3m}+2^{m+1}}{3}\).
Это уже олимпиадный фильтр по остаткам; стоит давать после фильтра четности.