MathDB

For an integer

m

, denote by

t(m)

the unique number in

\{1, 2, 3\}

such that m \plus{} t(m) is a multiple of

3

. A function

f: \mathbb{Z}\to\mathbb{Z}

satisfies f( \minus{} 1) \equal{} 0, f(0) \equal{} 1, f(1) \equal{} \minus{} 1 and f\left(2^{n} \plus{} m\right) \equal{} f\left(2^n \minus{} t(m)\right) \minus{} 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

Problem Statement