Balkan 02/4 solution

19th Balkan 2002

Problem 4

N is the set of positive integers. Find all functions f: N → N such that f( f(n) ) + f(n) = 2n + 2001 or 2n + 2002.

Solution

Obviously one solution is f(n) = n + 667. We show that there are no others.

Define the sequence a_n by a₁ = k, a_n+1 = f(a_n). Put b_m = a_m - a_m-1 - 667. Then b_m+1 + 2b_m = a_m+1 + a_m - 2a_m-1 - 2001 = 0 or 1, using the given relation with n = a_m-1.

So if b_n ≥ k > 0, then b_n+1 ≤ -(2k-1) and b_n+2 ≥ 4k-2 ≥ 2k (*). So if b₂ > 0, then b_2n ≥ 2ⁿ. For sufficiently large n this is > 1335. So for sufficiently large n we have b_2n > 1335. Hence b_2n + b_2n+1 = - b_2n or -b_2n + 1 < -1334. But b_2n + b_2n+1 = a_2n+1 - a_2n-1 - 1334, so a_2n+1 < a_2n-1. So after a while the odd terms become negative. Contradiction. So b₂ ≤ 0.

But if b₂ < 0, then b₃ > 0 and the same argument shows that the even terms become negative.. Contradiction. Hence b₂ = 0. In other words a₂ = a₁ + 667. But a₁ was chosen arbitrarily to be k, and a₂ = f(k). So we have proved that f(k) = k + 667, as required.

Many thanks to Xin Tao for pointing out an error in the original solution.

19th Balkan 2002