For an integer
![m](/media/m/1/3/6/1361d4850444c055a8a322281f279b39.png)
, denote by
![t(m)](/media/m/5/2/5/5251a3270d172456b29036c237526af9.png)
the unique number in
![\{1, 2, 3\}](/media/m/4/c/c/4ccd4e3eda9a6bd7a88ff4e73761ce04.png)
such that
![m + t(m)](/media/m/8/4/8/84832402abc04c4e746bf5c039d3d556.png)
is a multiple of
![3](/media/m/b/8/2/b82f544df38f2ea97fa029fc3f9644e0.png)
. A function
![f: \mathbb{Z}\to\mathbb{Z}](/media/m/9/2/e/92e9d6792f73b540c281a8d7ad423cb3.png)
satisfies
![f( - 1) = 0](/media/m/3/d/6/3d69b3189551a67a4a3dc12b48737bc9.png)
,
![f(0) = 1](/media/m/2/f/8/2f8d7e5312aeea192bbf7dd6a5556409.png)
,
![f(1) = - 1](/media/m/7/8/1/78195245d4dd918aa90f6b046521c142.png)
and
![f\left(2^{n} + m\right) = f\left(2^n - t(m)\right) - f(m)](/media/m/9/8/6/986baec012b80567362ef47755919cd3.png)
for all integers
![m](/media/m/1/3/6/1361d4850444c055a8a322281f279b39.png)
,
![n\ge 0](/media/m/2/1/7/2178fcb2466fe734ce659338827c1632.png)
with
![2^n > m](/media/m/c/4/1/c4167a8860814d258e08e571d9344b3f.png)
. Prove that
![f(3p)\ge 0](/media/m/7/0/f/70f4ae10282808e2949192b477df765e.png)
holds for all integers
![p\ge 0](/media/m/c/2/7/c27887ada3b7d39323e46ec601c92152.png)
.
Proposed by Gerhard Woeginger, Austria
%V0
For an integer $m$, denote by $t(m)$ the unique number in $\{1, 2, 3\}$ such that $m + t(m)$ is a multiple of $3$. A function $f: \mathbb{Z}\to\mathbb{Z}$ satisfies $f( - 1) = 0$, $f(0) = 1$, $f(1) = - 1$ and $f\left(2^{n} + m\right) = f\left(2^n - t(m)\right) - f(m)$ for all integers $m$, $n\ge 0$ with $2^n > m$. Prove that $f(3p)\ge 0$ holds for all integers $p\ge 0$.
Proposed by Gerhard Woeginger, Austria