Turkish Mathematical Olympiad

Using the fact that
$$Q(x)^{7^m} \equiv Q(x^{7^m}) \pmod{7}$$
for all polynomials $Q(x)$ with integer coefficients and for all positive integers $m$, we see that the integers $n = 7^k$ and $n = 7^k + 7^l$ with $0 \le k \le l$ satisfy the condition of the problem.

Now we will show that if $n$ is not of this form, then it does not satisfy the condition of the problem. Without loss of generality we may assume that $n$ is not divisible by $7$.

As $n > 2$, the coefficient of $x^3$ in $P_n(x)$ is $n(n-1)$. If $7|n(n-1)$, then $7|n-1$. Let $a \ge 1$ and $b \ge 2$ be integers such that $7 \nmid b$ and $n = 1 + 7^a b$. Then we have

the following set of congruences modulo $7$:
$$(x^2 + x + 1)^n \equiv (x^2 + x + 1)(x^2 + x + 1)^{7^a} \equiv (x^2 + x + 1)(x^{2 \cdot 7^a} + x^{7^a} + 1)^b \\ \equiv 1 + x + x^2 + b x^{7^a} + b x^{7^a+1} + b x^{7^a+2} \\ \qquad + \text{(terms of order } 2 \cdot 7^a \text{ or larger)}$$
$$(x+1)^n \equiv 1 + x + b x^{7^a} + b x^{7^a+1} + \text{(terms of order } 2 \cdot 7^a \text{ or larger)}$$
$$(x^2 + 1)^n \equiv 1 + x^2 + \text{(terms of order } 2 \cdot 7^a \text{ or larger)}$$
$$(x^2 + x)^n \equiv \text{(sum of terms of order } 2 \cdot 7^a \text{ or larger)}$$
(In the last congruence we used the fact that $b \ge 2$.) Putting these together we get
$$P_n(x) \equiv b x^{7^a+2} + \text{(terms of order } 2 \cdot 7^a \text{ or larger)} \pmod{7}.$$
Since $b$ is not divisible by $7$, the coefficient of $x^{7^a+2}$ in $P_n(x)$ is not divisible by $7$.