Let $S={1, 2, 3, 4, ....., 2070}$ find the number of subsets of $S$ whose sum of elements in $S$ is divisible by 9

Solution 1:

In general, if $f$ is a polynomial, and $\zeta=e^{i2\pi/n}$ is a primitive $n^{th}$ root of unity, then $\frac1n\sum_{k=0}^{n-1}f(\zeta^k)$ is equal to the sum of the coefficients of powers of $x^{n}$. In our case, let $\zeta=e^{i2\pi/9}$. The periodic nature of the powers of $\zeta$ implies $$ f(\zeta^k)=\Big((1+\zeta)(1+\zeta^2)\cdots(1+\zeta^9)\Big)^{230}\tag 1 $$ To proceed, we use this lemma.

Lemma: If $\omega$ is a primitive $n^{th}$ root of unity, and $n$ is odd, then $$(1+\omega)(1+\omega^2)\cdots(1+\omega^n)=2.$$

Proof: It is well known that the distinct roots of the polynomial $x^n-1$ are exactly $\omega^k$, for $k=0,1,\dots,n-1$. Therefore, $x^n-1$ factors as $$ x^n-1=(x-1)(x-\omega)(x-\omega^2)\cdots(x-\omega^{n-1}) $$ Conclude by setting $x=-1$. $\square$

Back to the problem at hand, $\zeta,\zeta^2,\zeta^4,\zeta^5,\zeta^7,\zeta^8$ are all primitive $9^{th}$ roots of unity, so applying the Lemma to $(1)$ implies $$ f(\zeta^k)=2^{230},\qquad k\in \{1,2,4,5,7,8\} $$ However, for $k=3,6$, $\zeta^k$ is a primitive third root of unity, and we instead have $$ f(\zeta^3)=f(\zeta^6)=\Big((1+\zeta^3)(1+\zeta^6)(1+\zeta^9)\Big)^{690}=2^{690} $$ Finally, we obviously have $f(\zeta^0)=f(1)=2^{2070}$. Putting this all together, we get $$ \text{sum of coefficients of $x^{9k}$}=\frac19\sum_{k=0}^{9-1}f(\zeta^k)=\frac19\Big(2^{2070}+2\cdot 2^{690}+6\cdot 2^{230}\Big) $$

Solution 2:

Let $g(n,j)$ be the number of subsets of $\{1,\ldots,n\}$ whose sum $\equiv j \bmod 9$. Then $g(n+1,j) = g(n,j) + g(n,j-(n+1))$.

I find that $$ \pmatrix{g(9k+9,0)\cr g(9k+9, 1)\cr g(9k+9,2)\cr g(9k+9,3)\cr g(9k+9,4)\cr g(9k+9,5)\cr g(9k+9,6)\cr g(9k+9,7)\cr g(9k+9,8)\cr} = \pmatrix{ \begin {array}{ccccccccc} 60&56&56&58&56&56&58&56&56 \\ 56&60&56&56&58&56&56&58&56\\ 56 &56&60&56&56&58&56&56&58\\ 58&56&56&60&56&56&58&56& 56\\56&58&56&56&60&56&56&58&56\\ 56&56&58&56&56&60&56&56&58\\ 58&56&56&58&56&56&60&56 &56\\56&58&56&56&58&56&56&60&56 \\ 56&56&58&56&56&58&56&56&60\end {array} } \pmatrix{g(9k,0)\cr g(9k, 1)\cr g(9k,2)\cr g(9k,3)\cr g(9k,4)\cr g(9k,5)\cr g(9k,6)\cr g(9k,7)\cr g(9k,8)\cr}$$ The matrix turns out to diagonalize quite nicely, and I get $$g(9k, 0) = \frac{512^k + 2 \cdot 8^k + 6 \cdot 2^k}{9}$$ Thus as $2070 = 9 \cdot 230$, the answer is $$ \frac{512^{230} + 2 \cdot 8^{230} + 6 \cdot 2^{230}}{9}$$