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$.
 A: Define the polynomials
$$
L_i(x) = \underset{j \neq i}{\prod_{0 \le j \le n}} \frac{(x-x_j)}{(x_i - x_j)} = 
\begin{cases}
1 & \text{ if } x = i \\
0 & \text{ if } x = j \neq i 
\end{cases}
$$
for each $i \in \{0,1,\cdots,3n\}$. It follows that since the $L_i$'s have degree $3n$, we have (I leave the computations up to you) :
$$
P(x) = \sum_{i=0}^{3n} P(i) L_i(x) = \sum_{i=0}^n 2 (-1)^{n-i} \binom x{3i} \binom {x-(3i+1)}{3(n-i)} - \sum_{i=0}^{n-1} (-1)^{n-i}\binom x{3i+1}\binom{x-(3i+2)}{3(n-i)-1}.
$$
You can evaluate $P(3n+1)$ for a long range using a computer (the notation $\binom xi = x(x-1)\cdots(x-(i-1))/i!$ implies that $\binom xi (n) = \binom ni$ for positive integers). In other words, you are looking for $n$ such that 
$$
730 = P(3n+1) = 2 \sum_{i=0}^n (-1)^{n-i} \binom{3n+1}{3i} - \sum_{i=0}^{n-1} (-1)^{n-i} \binom{3n+1}{3i+1} \\
= \sum_{i=0}^n \left( (-1)^{n-i} \left[ 2\binom{3n+1}{3i} - \binom{3n+1}{3i+1} \right] \right) 
$$
Hope that helps,
A: The OP is equivalent to:
given
\begin{align} 
P(x)&=\sum_{i=0}^{3n} a_i x^i
\tag{1}\label{1}
,\\
P(3i-2)&=1,\quad i=1,\cdots,n
\tag{2}\label{2}
;\\
P(3i-1)&=0,\quad i=1,\cdots,n
\tag{3}\label{3}
;\\
P(3i)&=2,\quad i=1,\cdots,n
\tag{4}\label{4}
;\\
P(3n+1)&=730
\tag{5}\label{5}
;\\
P(0)&=2
\tag{6}\label{6}
,
\end{align}  
determine $n$.
Conditions \eqref{2}-\eqref{5}
define
the
system of 
$(3n+1)\times(3n+1)$
linear equations,
\begin{align}
Au&=v
\tag{7}\label{7}
, 
\end{align}
where $A$ is
a special case of
the
$(3n+1)\times(3n+1)$ 
Vandermonde matrix
\begin{align}
A&=\begin{bmatrix}
1&1&1&\dots &1
\\
1&2^1&2^2&\dots &2^{3n}
\\
1&3^1&3^2&\dots &3^{3n}
\\
\vdots &\vdots &\vdots &\ddots &\vdots 
\\
1&(3n+1)^1&(3n+1)^2&\dots &(3n+1)^{3n}\\
\end{bmatrix}
,\\
\text{or }\quad A_{ij}&=(i+1)^{j}
,\quad i,j=0,\cdots,3n
.
\end{align}
$u$ is the vector of coefficients $a_i$
\begin{align}
u&=[a_0,\cdots,a_{3n}]^{\mathsf{T}}
,
\end{align}  
and the right-hand side of 
\eqref{7} is
a vector of the form
\begin{align}
v&=[\underbrace{1,0,2,1,0,2,\cdots,1,0,2}_{3n},730]^{\mathsf{T}}
,\\
\text{or }\quad 
v_{3n}&=730
,\\
v_{i}&= 2-(i+1\mod 3)
,\quad i=0,\cdots,3n-1
.
\end{align}
It follows from the condition 
\eqref{6}
that
\begin{align}
a_0&=2
,
\end{align}
For any $n$
all the coefficients $a_i$
of $P(x)$,
including $a_0$,
can be found as the solution 
of \eqref{7}.
A quick test reveals that 
$a_0=2$
for $n=4$.
This is a log of Maxima session for the test:
(%i1) a[i,j]:=(i+1)^j$
(%i2) v[i]:=2-mod(i+1,3)$
(%i3) n:4$
(%i4) A:apply('matrix,makelist(makelist(a[i,j],j,0,3*n),i,0,3*n))$
(%i5) V:makelist(v[i],i,0,3*n)$
(%i6) V[3*n+1]:730$
(%i7) V;
(%o7)              [1, 0, 2, 1, 0, 2, 1, 0, 2, 1, 0, 2, 730]
(%i8) a0=invert(A)[1] . V;
(%o8)                               a0 = 2

A: 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.
