IMO 1988 Problem A3 A function f is defined on the positive integers by: f(1) = 1; f(3) = 3; f(2n) = f(n), f(4n + 1) = 2f(2n + 1) - f(n), and f(4n + 3) = 3f(2n + 1) - 2f(n) for all positive integers n. Determine the number of positive integers n less than or equal to 1988 for which f(n) = n. Solution
: 92. f(n) is always odd. If n = b r+1 b r ...b 2 b 1 b 0 in binary and n is odd, so that b r+1 = b 0 = 1, then f(n) = b r+1 b 1 b 2 ...b r b 0 . If n has r+2 binary digits with r > 0, then there are 2 [(r+1)/2] numbers with the central r digits symmetrical, so that f(n) = n (because we can choose the central digit and those lying before it arbitarily, the rest are then determined). Also there is one number with 1 digit (1) and one number with two digits (3) satisfying f(n) = 1. So we find a total of 1 + 1 + 2 + 2 + 4 + 4 + 8 + 8 + 16 + 16 = 62 numbers in the range 1 to 1023 with f(n) = n. 1988 = 11111000011. So we also have all 32 numbers in the range 1023 to 2047 except for 11111111111 and 11111011111, giving another 30, or 92 in total. It remains to prove the assertions above. f(n) odd follows by an easy induction. Next we show that if 2 m < 2n+1 < 2 m+1 , then f(2n+1) = f(n) + 2 m . Again we use induction. It is true for m = 1 (f(3) = f(1) + 2). So suppose it is true for 1, 2, ... , m. Take 4n+1 so that 2 m+1 < 4n+1 < 2 m+2 , then f(4n+1) = 2f(2n+1) - f(n) = 2(f(n) + 2 m ) - f(n) = f(n) + 2 m+1 = f(2n) + 2 m+1 , so it is true for 4n+1. Similarly, if 4n+3 satisfies, 2 m+1 < 4n+3 < 2 m+2 , then f(4n+3) = 3f(2n+1) - 2f(n) = f(2n+1) + 2(f(n) + 2 m ) - 2f(n) = f(2n+1) + 2 m+1 , so it is true for 4n+3 and hence for m+1. Finally, we prove the formula for f(2n+1). Let 2n+1 = b r+1 b r ...b 2 b 1 b 0 with b 0 = b r+1 = 1. We use induction on r. So assume it is true for smaller values. Say b 1 = ... = b s = 0 and b s+1 = 1 (we may have s = 0, so that we have simply b 1 = 1). Then n = b r+1 ... b 1 and f(n) = b r+1 b s+2 b s+3 ...b r b s+1 by induction. So f(n) + 2 r+1 = b r+1 0...0b r+1 b s+2 ...b r b s+1 , where there are s zeros. But we may write this as b r+1 b 1 ...b s b s+1 ...b r b r+1 , since b 1 = ... = b s = 0, and b s+1 = b r+1 = 1. But that is the formula for f(2n+1), so we have completed the induction. Solutions are also available in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X. 29th IMO 1988 © John Scholes jscholes@kalva.demon.co.uk 21 Oct 1998