Question 84
For each positive integer $k$, define $r(k)$ as the number of runs of $k$ in base-2, where a run is a collection of consecutive 0s or consecutive 1s without a larger one containing it. For example, $(11100100)_2$ has 4 runs, namely $111-00-1-00$. Also, $r(0) = 0$. Given a positive integer $n$, find all functions $f: \mathbb{Z} \to \mathbb{Z}$ such that
$$
\sum_{k=0}^{2^n-1} 2^{r(k)} f(k + (-1)^k x) = (-1)^{x+n} \quad \text{for all integer } x.
$$
$$
\sum_{k=0}^{2^n-1} 2^{r(k)} f(k + (-1)^k x) = (-1)^{x+n} \quad \text{for all integer } x.
$$