This problem will so easy if participant try with $n=0,1,2$. We induction with $n\geq 0$ that only: $f(x)=(-1)^x \forall \ x\in \mathbb{Z}$ (1) Easily see (1) true with $n=0$. Suppose (1) true with $n-1$, we prove (1) true with $n \geq 1$. See that, with $0\leq a \leq 2^{n-1}-1 ; b= 2^{n}-1-a$ $\Rightarrow r(b)=r(a)+1$ (easy check) and $(-1)^a = - (-1)^b$ (because $a\ne b$ in modulo $2$) Set $g(x) = - f(x) - 2f(2^n-1-x)$ $g: \mathbb{Z} \to \mathbb{Z}$ From $\sum_{k=0}^{2^n-1} 2^{r(k)}f(k+(-1)^{k} x)=(-1)^{x+n}$ $\Rightarrow \sum_{k=0}^{2^{n-1}-1} 2^{r(k)}(f(k+(-1)^{k} x)+2f(2^n-1-k+(-1)^{2^n-1-k})=(-1)^{x+n}$ $\Rightarrow \sum_{k=0}^{2^{n-1}-1} 2^{r(k)}g(x+(-1)^kx)=(-1)^{x+n-1}$ With induction, we have: $g(x) = (-1)^x \forall \ x\in\mathbb{Z}$ So $f(x) + 2f(2^n-1-x) = (-1)^{x+1}$ So $f(2^n-1-x) + 2f(x) = (-1)^{x}$ $\Rightarrow f(x) = \dfrac{2(-1)^x - (-1)^{x+1}}{3} = (-1)^x$