39th BMO 2003 Problem 4 Let X be the set of non-negative integers and f : X → X a map such that ( f(2n+1) ) 2 - ( f(2n) ) 2 = 6 f(n) + 1 and f(2n) >= f(n) for all n in X. How many numbers in f(X) are less than 2003?
128 Solution Obviously f(2n) + 3 > f(2n+1) > f(2n), so f(2n+1) = f(2n) + 1 or f(2n) + 2. But f(2n) 2 + 6 f(n) + 1 and f(2n) 2 have opposite parity, so we must have f(2n+1) = f(2n) + 1. Hence f(2n) = 3 f(n). So, in particular, f(0) = 0. Hence f(1) = 1. A trivial induction now gives that f is strictly monotonic increasing. Obviously f(128) = 3 7 = 2187 > 2003. f(127) = f(126) + 1 = 3 f(63) + 1 = 3 f(62) + 4 = 9 f(31) + 4 = 9 f(30) + 13 = 27 f(15) + 13 = 27 f(14) + 40 = 81 f(7) + 40 = 81 f(6) + 121 = 243 f(3) + 121 = 243 f(2) + 364 = 729 f(1) + 364 = 1093 < 2003. So the 128 distinct numbers f(0), f(1), ... , f(127) are less than 2003. 39th BMO 2003 © John Scholes jscholes@kalva.demon.co.uk 2 Mar 2003 Last corrected/updated 2 Mar 03