MathDB

Prove g(k-1)=g(k)=g(k+1) for non-decreasing g is impossible

Source: Greece MO 1998

May 27, 2011

functioninductionfloor functionalgebra proposedalgebra

Problem Statement

Let a function

g:\mathbb{N}_0\to\mathbb{N}_0

satisfy

g(0)=0

and

g(n)=n-g(g(n-1))

for all

n\ge 1

. Prove that:
a)

g(k)\ge g(k-1)

for any positive integer

k

. b) There is no

k

such that

g(k-1)=g(k)=g(k+1)