The polynomial of degree $k$ such that $f(0)=0,f(1)=1,f(2)=0,\cdots,f(k-1)=0,f(k)=1$ with satisfy the conditions. You can prove with induction by $k$(use diffenerces) that $f(x)\equiv 0,\texttt{x is even}(\mod 2^k);f(x)\equiv 1(\mod 2^k),\texttt{x is odd}$. Which is also right for $k$ is even.

zhaobin wrote: You can prove with induction by $k$(use diffenerces) that $f(x)\equiv 0,\texttt{x is even}(\mod 2^k);f(x)\equiv 1(\mod 2^k),\texttt{x is odd}$. Yes; this kind of construction is a special case of a problem I posted here, where $n=2$, $m=2^k$, and $(a_1,a_2)=(1,0)$. In this particular case, we have $f(x)=\sum_{i=1}^{k}\binom{x}{i}(-2)^{i-1}$ by Newton interpolation; using the identity \[\binom{x+2}{i}=\binom{x}{i}\binom{2}{0}+\binom{x}{i-1}\binom{2}{1}+\binom{x}{i-2}\binom{2}{2}\]for $i\ge2$, we find that \[f(x+2)-f(x)=-\binom{x}{k-1}(-2)^k\equiv0\pmod{2^k}\]for all $x$, and of course $f(0)=0$ and $f(1)=1$ by construction. Does anyone know why the problem has the extra "non-integer coefficients" restriction (I assume we need all nonzero coefficients to be non-integer)? It seems rather artificial, but for $k\ge4$, it's easy to do, since we can preserve all the desired properties by taking \[g(x)=\sum_{i=1}^{k}\binom{x}{i}(c_i 2^k + (-2)^{i-1})\]instead for some integers $c_1,\ldots,c_k\in\{0,1,2\}$, where $c_1=c_2=0$ ($c_1=0$ preserves $g(1)=1$ and changing $c_2$ doesn't do anything). Indeed, since $3\mid i!$ for $3\le i\le k$, we first easily deal with $c_k,c_{k-1},\ldots,c_5$ in this order: take $c_k=0$ so that $[x^k]g(x)\notin\mathbb{Z}$, and for $i\in[5,k-1]$, if we have already chosen $c_k,\ldots,c_{i+1}$, then since $2^k\perp 3$, some choice of $c_i\in\{0,1,2\}$ (in fact, at least two) must make $[x^k]g(x)\notin\mathbb{Z}$. However, for $c_3,c_4$ we need to be slightly more careful: since $\binom{x}{1}=x$ and $2\binom{x}{2}=x^2-x$ have integer coefficients, the only way we can make sure $[x^1]$ and $[x^2]$ are not integers is through \[\binom{x}{3}(c_3 2^k + (-2)^2) = \frac{x^3+2x}{3}(2+c_3 2^{k-1})-x^2(2+c_3 2^{k-1})\](which only affects $[x^3],[x^1]$) and \[\binom{x}{4}(c_4 2^k + (-2)^3) = \frac{x^4+11x^2}{3}(-1+c_4 2^{k-3})-(x^3+x)(-2+c_4 2^{k-2})\](which only affects $[x^4],[x^2]$). Once $c_5$ through $c_k$ have been chosen, at least two choices of $c_4\in\{0,1,2\}$ must make $[x^4]$ non-integer and at least two must make $[x^2]$ non-integer, so by pigeonhole we can take the one that works for both. Similarly we can choose $c_3$, so we're done unless $k=3$. However, the $[x^2]$ term screws this method up for $k=3$. Maybe I'm missing something obvious though.