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.
Obviously one solution is f(n) = n + 667. We show that there are no others. Define the sequence a n by a 1 = 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 2 > 0, then b 2n ≥ 2 n . 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  0 and the same argument shows that the even terms become negative.. Contradiction. Hence b 2 = 0. In other words a 2 = a 1 + 667. But a 1 was chosen arbitrarily to be k, and a 2 = 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 © John Scholes jscholes@kalva.demon.co.uk 16 June 2002