Advanced book on Mathematics Olympiad

Number Theory 685

This proves the claim and completes the solution.
(34th International Mathematical Olympiad, 1993)

723.Suppose first that the pair(f, g)is not unique and that there is a second pair of func-
tions(f′,g′)subject to the same conditions. Write the sets{f (n), n≥ 1 }∪{g(n), n≥ 1 },
respectively,{f′(n), n≥ 1 }∪{g′(n), n≥ 1 }, as increasing sequences, and letn 0 be the
smallest number where a difference occurs in the values off (n)andg(n)versusf′(n)and
g′(n). Because the pairs of functions exhaust the positive integers, eitherf(n 1 )=g′(n 0 )
orf′(n 0 )=g(n 1 ). The situations are symmetric, so let us assume that the first occurs.
Then

f(n 1 )=g′(n 0 )=f′(f′(kn 0 ))+ 1 =f(f(kn 0 ))+ 1 =g(n 0 ).

We stress that the third equality occurs becausef′(kn 0 )occurs earlier in the sequence
(since it is smaller thanf(n 1 )), so it is equal tof(kn 0 ), and the same is true for
f′(f′(kn 0 )). But the equalityf(n 1 )=g(n 0 )is ruled out by the hypothesis, which
shows that our assumption was false. Hence the pair(f, g)is unique.
Inspired by the previous problems we takeαto be the positive root of the quadratic
equationkx^2 −kx− 1 =0, and setβ=kα^2. Thenα^1 +β^1 =1, and becausekis an
integer, bothαandβare irrational. By Beatty’s theorem the sequencesf (n)=αn
andg(n)=βnare strictly increasing and define a partition of the positive integers
into two disjoint sets. Let us show thatfandgsatisfy the functional equation from the
statement.
Becausekα^2 =kα+1,

g(n)=kα^2 n=(kα+ 1 )n=kαn+n,

and we are left to prove thatαkn+n=ααkn +1, the latter beingf(f(kn))+1.
Reduce this further to

(α− 1 )αkn =n− 1.

Since(α− 1 )αk=1 andαis irrational,(α− 1 )αkn<n. Also,

(α− 1 )αkn>(α− 1 )(αkn− 1 )=(α^2 k−αk)n+ 1 −α=n+ 1 −α>n− 1 ,

sinceα<2 (which can be checked by solving the quadratic equation that definesα).
Hence

g(n)=αkn+n=ααn + 1 =f(f(kn))+ 1 ,

and the problem is solved.