Classical use of generating functions. Consider $P(x) = 2\prod_{k=1}^9 (1+x^k) = \sum_{j=0}^{45} a_jx^j$. The number $N$ we look for is $N = 1+ \sum_{\ell=1}^{15} a_{3\ell}$. But for $\omega = \cos \dfrac {2\pi}{3} + \textrm{i}\sin \dfrac {2\pi}{3}$ we have $P(1) + P(\omega)+P(\omega^2) = 6 + 3\sum_{\ell=1}^{15} a_{3\ell}$, so $N = \dfrac {1} {3}(P(1) + P(\omega)+P(\omega^2)) -1$. It is easy to compute $P(1) = 2^{10}$ and $P(\omega)=P(\omega^2) = 2^4$, thus $\boxed{N = 351}$.

Can anyone provide a solution without using generating functions?

Wavefunction wrote: Can anyone provide a solution without using generating functions? check the official solution.

Wavefunction wrote: Can anyone provide a solution without using generating functions? This problem essentially has the same solution idea.

a solution without genrating function- dividing the set of 0 to 9 (lets call it S in my answer)into three categories- 1)3k type- {0,3,6,9} 2)3k+1 type- {1,4,7} 3) 3k+2 type- {2,5,8} now in any subset of S ,3k type numbers do not contribute anything in divisibilty so subsets of S containig just 3k type numbers are $2^4 -1 $, now we just have to look at the cases with 3k+2 and 3k+1 type numbers when sum of these is divisible by 3 adding a,b,c,d and e we get 21 now we will multiply $ 2^4 $ with 21 (we multiplied it include the presence/absence of 3k type numbers) we get 336 adding all- $336+ 2^4-1= 351$ which is our requird answer. my first solution on AoPS

Attachments:

note- although in the image its written no of subsets its actually no of ways of choosing elements from 3k+1 and 3k+2 type numbers