MathDB
f(n) - n is periodic

Source: IMO 2015 Shortlist, N6

July 7, 2016
functionnumber theoryperiodic functionIMO Shortlistarrows

Problem Statement

Let Z>0\mathbb{Z}_{>0} denote the set of positive integers. Consider a function f:Z>0→Z>0f: \mathbb{Z}_{>0} \to \mathbb{Z}_{>0}. For any m,n∈Z>0m, n \in \mathbb{Z}_{>0} we write fn(m)=f(f(…f⏟n(m)…))f^n(m) = \underbrace{f(f(\ldots f}_{n}(m)\ldots)). Suppose that ff has the following two properties:
(i) if m,n∈Z>0m, n \in \mathbb{Z}_{>0}, then fn(m)−mn∈Z>0\frac{f^n(m) - m}{n} \in \mathbb{Z}_{>0}; (ii) The set Z>0∖{f(n)∣n∈Z>0}\mathbb{Z}_{>0} \setminus \{f(n) \mid n\in \mathbb{Z}_{>0}\} is finite.
Prove that the sequence f(1)−1,f(2)−2,f(3)−3,…f(1) - 1, f(2) - 2, f(3) - 3, \ldots is periodic.
Proposed by Ang Jie Jun, Singapore
Back to ProblemsView on AoPS