Taiwan IMO Selection Camp

Let $P(x), Q(x)$ be polynomials with integer coefficients. If all coefficients of $P(x) - Q(x)$ are even, then the two polynomials are said to be similar, denoted by $P(x) \sim Q(x)$. In this case, the polynomials $P(x), Q(x)$ have the same number of terms with odd coefficients; denote the number of odd coefficients of the polynomial $P(x)$ by $\beta(P)$. Clearly,
$$(x^2 - x + 1)^n \sim (x^2 + x + 1)^n.$$
Below we discuss the problem of the number of odd coefficients of $P_n(x) = (x^2 + x + 1)^n$.

Use mathematical induction to prove: when $n = 2^q$ ($q$ a positive integer), $P_n(x) \sim x^{2n} + x^n + 1$. In this way, one can convert the positive integer $n$ into binary. First consider a simple case: $n = 2^m - 1, m$ a positive integer.

Let $m = 2k + 1, k$ be an integer greater than or equal to 0. Then
$$n = 2^{2k+1} - 1 \equiv 1 \pmod{3}.$$
Consider the polynomial
$$R(x) = (x+1) \left( \sum_{k=0}^{\frac{(n-1)}{3}} x^{n+3k} + \sum_{k=0}^{\frac{(n-4)}{3}} x^{3k} \right) + x^{n-1}.$$
Then $\beta(R) = \frac{2^{m+2}-1}{3}$.
$$\begin{aligned} R(x)(x^2+x+1) &\sim (x+1) \left( \sum_{k=0}^{n+1} x^{n+k} + \sum_{k=0}^{n-2} x^k \right) + x^{n-1}(x^2+x+1) \\ &\sim x^{2n+2} + x^{n+1} + 1, \end{aligned}$$
and $P_n(x)(x^2+x+1) \sim x^{2n+2} + x^{n+1} + 1$.
Hence $\beta(P_n) = \beta(R) = \frac{2^{m+2}+1}{3}$.

Now let $m = 2k + 1, k$ be a positive integer. Then
$$n = 2^{2k} - 1 \equiv 0 \pmod{3}.$$
Consider the polynomial
$$Q(x) = (x+1) \sum_{k=0}^{\frac{(n-3)}{3}} (x^{n+2+3k} + x^{3k}) + x^n.$$
Similarly $\beta(P_n) = \beta(Q) = \frac{2^{m+2}-1}{3}$.
Hence $\beta(P_{2^m-1}(x)) = \frac{2^{m+2} + (-1)^{m+1}}{3}$.

Next consider the general case: express the positive integer $n$ in binary,
$$n = (\underbrace{11\cdots1}_{a_k \text{ digits}} \underbrace{00\cdots0}_{b_k \text{ digits}} \underbrace{11\cdots1}_{a_{k-1} \text{ digits}} \underbrace{00\cdots0}_{b_{k-1} \text{ digits}} \cdots \underbrace{11\cdots1}_{a_1 \text{ digits}} \underbrace{00\cdots0}_{b_1 \text{ digits}})_2,$$
where $a_i, b_i$ are positive integers, $b_1 \ge 0$.
$$\text{Let } S_i = \sum_{j=1}^{i-1} (b_j + a_j) + b_i \text{ (i = 1, 2, \dots, k).}$$
$$\text{Then } n = \sum_{i=1}^{k} 2^{S_i}(2^{a_i} - 1),$$
$$P_n(x) = \prod_{i=1}^{k} (x^2 + x + 1)^{2^{S_i} (2^{a_i} - 1)}$$
$$\sim \prod_{i=1}^{k} (x^{2^{S_i+1}} + x^{2^{S_i}} + 1)^{2^{a_i}-1}.$$
Therefore
$$\beta(P_n) = \prod_{i=1}^{k} \frac{2^{a_i+2} - (-1)^{a_i}}{3}.$$