1

Part of 2007 Serbia National Math Olympiad

Problems(1)

sequence of functions on N

Source: Serbian Mathematical Olympiad 2007

k

be a natural number. For each function

f : \mathbb{N}\to \mathbb{N}

define the sequence of functions

(f_{m})_{m\geq 1}

f_{1}= f

f_{m+1}= f \circ f_{m}

m \geq 1

f

k

-nice if for each

n \in\mathbb{N}: f_{k}(n) = f (n)^{k}

. (a) For which

k

does there exist an injective

k

f

? (b) For which

k

does there exist a surjective

k

f

functioninductionalgebra proposedalgebra