### 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

f(n) is always odd. If n = br+1br...b2b1b0 in binary and n is odd, so that br+1 = b0 = 1, then f(n) = br+1b1b2...brb0. 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 2m < 2n+1 < 2m+1, then f(2n+1) = f(n) + 2m. 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 2m+1 < 4n+1 < 2m+2, then f(4n+1) = 2f(2n+1) - f(n) = 2(f(n) + 2m) - f(n) = f(n) + 2m+1 = f(2n) + 2m+1, so it is true for 4n+1. Similarly, if 4n+3 satisfies, 2m+1 < 4n+3 < 2m+2, then f(4n+3) = 3f(2n+1) - 2f(n) = f(2n+1) + 2(f(n) + 2m) - 2f(n) = f(2n+1) + 2m+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 = br+1br...b2b1b0 with b0 = br+1 = 1. We use induction on r. So assume it is true for smaller values. Say b1 = ... = bs = 0 and bs+1 = 1 (we may have s = 0, so that we have simply b1 = 1). Then n = br+1 ... b1 and f(n) = br+1bs+2bs+3...brbs+1 by induction. So f(n) + 2r+1 = br+10...0br+1bs+2...brbs+1, where there are s zeros. But we may write this as br+1b1...bsbs+1...brbr+1, since b1 = ... = bs = 0, and bs+1 = br+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.