The question is
How many of the coefficients of $(1+x+x^2)^{2018}$ are not divisible by 3?
Somebody asked me the question, and I have no idea how to solve it. I am not sure if the coefficients are known to have a closed form either.
I guess that the question might be solvable using a combinatorics way, but not sure either. Thanks.
If $p$ is a prime and $m \geq 1$, then by the Freshman's dream,
$$ (X + Y)^{p^m} \equiv X^{p^m} + Y^{p^m} \pmod{p}. $$
So, expanding $2018 = \sum_{k\geq 0} a_k 3^k$, then
\begin{align*} (1+x+x^2)^{2018} = \prod_{k \geq 0} \left( (1 + x + x^2)^{3^k} \right)^{a_k} \equiv \prod_{k \geq 0} \left( 1 + x^{3^k} + x^{2\cdot 3^k} \right)^{a_k} \pmod{3} \end{align*}
Now, from $ 2018 = 2 + 2\cdot3^2 + 2\cdot3^3 + 2\cdot3^5 + 2\cdot3^6 $, we have $a_k = 2$ when $k = 0, 2, 3, 5, 6$ and $a_k = 0$ otherwise. Moreover,
$$ \left( 1 + x^{3^k} + x^{2\cdot 3^k} \right)^{2} \equiv \left( 1 + 2x^{3^k} \right)\left(1 + 2 x^{3^{k+1}}\right) \pmod{3} $$
Plugging this back,
\begin{align*} (1 + x + x^2)^{2018} &\equiv \prod_{k \in \{0, 2, 3, 5, 6\}} \left( 1 + 2x^{3^k} \right)\left(1 + 2 x^{3^{k+1}}\right) \pmod{3} \\ &= (1 + 2x) (1 + 2x^3) (1 + 2x^{3^2}) (1 + 2x^{3^3})^2 \\ &\quad \times (1 + 2x^{3^4}) (1 + 2x^{3^5}) (1 + 2x^{3^6})^2 (1 + 2x^{3^7}) \\ &\equiv (1 + 2x^{3^0}) (1 + 2x^{3^1}) (1 + 2x^{3^2}) (1 + x^{3^3} + x^{2\cdot 3^3}) \\ &\quad \times (1 + 2x^{3^4}) (1 + 2x^{3^5}) (1 + x^{3^6} + x^{2\cdot 3^6}) (1 + 2x^{3^7}) \pmod{3} \end{align*}
If we expand the last product, no two terms have the same exponent, and so, there are total $2^6 \times 3^2 = 576$ terms with coefficients not divisible by $3$.