IMO 1988 SL 26

Origin: GBR

Problem

A function f defined on the positive integers (and taking positive integer values) is given by f(1) = 1, f(3) = 3, f(2n) = f(n), f(4n + 1) = 2f(2n + 1) −f(n), f(4n + 3) = 3f(2n + 1) −2f(n), for all positive integers n. Determine with proof the number of positive integers less than or equal to 1988 for which f(n) = n.

Solution

The overline in this problem will exclusively denote binary representa- tion. We will show by induction that if n = ckck−1 . . . c0 = k i=0 ci2i is the binary representation of n (ci \in{0, 1}), then f(n) = c0c1 . . . ck = k i=0 ci2k−i is the number whose binary representation is the palindrome of the binary representation of n. This evidently holds for n \in{1, 2, 3}.

Let us assume that the claim holds for all numbers up to n −1 and show it holds for n = ckck−1 . . . c0. We observe three cases: (i) c0 = 0 ⇒n = 2m ⇒f(n) = f(m) = 0c1 . . . ck = c0c1 . . . ck. (ii) c0 = 1, c1 = 0 ⇒n = 4m + 1 ⇒f(n) = 2f(2m + 1) −f(m) = 2 \cdot 1c2 . . . ck −c2 . . . ck = 2k + 2 \cdot c2 . . . ck −c2 . . . ck = 10c2 . . . ck = c0c1 . . . ck. (iii) c0 = 1, c1 = 1 ⇒n = 4m + 3 ⇒f(n) = 3f(2m + 1) −2f(m) = 3 \cdot 1c2 . . . ck −2 \cdot c2 . . . ck = 2k + 2k−1 + 3 \cdot c2 . . . ck −2 \cdot c2 . . . ck = 11c2 . . . ck = c0c1 . . . ck. We thus have to find the number of palindromes in binary representation smaller than 1998 = 11111000100. We note that for all m \inN the numbers of 2m- and (2m −1)-digit binary palindromes are both equal to 2m−1. We also note that 11111011111 and 11111111111 are the only 11-digit palindromes larger than 1998. Hence we count all palindromes of up to 11 digits and exclude the largest two. The number of n \leq1998 such that f(n) = n is thus equal to 1+1+2+2+4+4+8+8+16+16+32−2 = 92.