IMO 1988/A3 solution

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

Answer: 92.

f(n) is always odd. If n = b_r+1b_r...b₂b₁b₀ in binary and n is odd, so that b_r+1 = b₀ = 1, then f(n) = b_r+1b₁b₂...b_rb₀. 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+1b_r...b₂b₁b₀ with b₀ = b_r+1 = 1. We use induction on r. So assume it is true for smaller values. Say b₁ = ... = b_s = 0 and b_s+1 = 1 (we may have s = 0, so that we have simply b₁ = 1). Then n = b_r+1 ... b₁ and f(n) = b_r+1b_s+2b_s+3...b_rb_s+1 by induction. So f(n) + 2^r+1 = b_r+10...0b_r+1b_s+2...b_rb_s+1, where there are s zeros. But we may write this as b_r+1b₁...b_sb_s+1...b_rb_r+1, since b₁ = ... = 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