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

Answer: 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.

© John Scholes

jscholes@kalva.demon.co.uk

21 Oct 1998