Polynomial $P(x)$ such that $P(3k)=2$, $P(3k+1)=1$, $P(3k+2)=0$ for $k=0,1,2,\ldots,n-1$, $P(3n)=2$, and $P(3n+1)=730$ Let $n$ be a positive integer such that there exists a polynomial $P(x)$ over $\mathbb{Q}$ of degree $3n$ satisfying the conditions below: 
$$P(0) = P(3) = \ldots = P(3n) = 2\,,$$
$$P(1) = P(4) = \ldots= P(3n - 2) = 1\,,$$
$$P(2) = P(5) = \ldots = P(3n - 1) = 0\,,$$
and 
$$P(3n + 1) = 730\,.$$
Determine the value of $n$.

Let $\omega:=\exp\left(\frac{2\pi\text{i}}{3}\right)=\frac{-1+\sqrt{-3}}{2}$.  Define $$\tau(z):=\left(\frac{1-\omega^2}{3}\right)z^2+\left(\frac{1-\omega}{3}\right)z+1\text{ for all }z\in\mathbb{C}\,.$$
Note that, for each $k\in\mathbb{Z}$, we have
$$\tau(\omega^k)=\left\{
\begin{array}{ll}
2&\text{if }k\equiv0\pmod{3}\,,\\
1&\text{if }k\equiv1\pmod{3}\,,\\
0&\text{if }k\equiv2\pmod{3}\,.
\end{array}
\right.$$  
It is well known (see also here) that, if $f(x)\in \mathbb{K}[x]$ is a polynomial over a field $\mathbb{K}$ of degree $d$, then
$$\sum_{r=0}^{d+1}\,(-1)^r\,\binom{d+1}{r}\,f(x+r)\equiv 0\,.$$
From the result above, we have that
$$\sum_{r=0}^{3n+1}\,(-1)^r\,\binom{3n+1}{r}\,P(r)=0\,.$$
Recall that $P(r)=\tau(\omega^r)$ for $r=0,1,2,\ldots,3n$, and $P(3n+1)=3^6+1=3^6+\tau(\omega^{3n+1})$.  That is,
$$\sum_{r=0}^{3n+1}\,(-1)^r\,\binom{3n+1}{r}\,\tau(\omega^r)=(-1)^{3n}\,3^6\,.$$
Ergo,
$$\left(\frac{1-\omega^2}{3}\right)\left(1-\omega^2\right)^{3n+1}+\left(\frac{1-\omega}{3}\right)\left(1-\omega\right)^{3n+1}+1(1-1)^{3n+1}=(-1)^{3n}3^6\,.$$
Thus,
$$2\,\text{Re}\left((1-\omega)^{3n+2}\right)=\left(1-\omega^2\right)^{3n+2}+\left(1-\omega\right)^{3n+2}=(-1)^{3n}3^7\,.$$
Since $1-\omega=\sqrt{-3}\,\omega^2$, we see that
$$(1-\omega)^{3n+2}=\sqrt{-3}^{3n+2}\omega^{6n+4}=\sqrt{-3}^{3n+2}\omega\,.$$
Therefore,
$$3^{\frac{3n+2}{2}}\,\text{Re}\left(\sqrt{-1}^{3n+2}\omega\right)=\text{Re}\left(\sqrt{-3}^{3n+2}\omega\right)=(-1)^{3n}\frac{3^7}{2}\,.$$
Since $\frac{1}{2}\leq \Big|\text{Re}\left(\sqrt{-1}^{3n+2}\omega\right)\Big|\leq\frac{\sqrt{3}}{2}$, we have that
$$\frac{3^{\frac{3n+2}{2}}}{2}\leq \frac{3^7}{2} \leq \frac{3^{\frac{3n+3}{2}}}{2}\,.$$
Consequently,
$$3n+2\leq 14\leq 3n+3\,.$$
This proves that $n=4$ is the only possibility.  It is not difficult to see that $n=4$ indeed works.
