26. (GBR 2) ${ }^{\mathrm{IMO} 3} \mathrm{~A}$ function $f$ defined on the positive integers (and taking positive integer values) is given by  $$ \begin{aligned} f(1) & =1, \quad f(3)=3 \\ f(2 n) & =f(n) \\ f(4 n+1) & =2 f(2 n+1)-f(n) \\ f(4 n+3) & =3 f(2 n+1)-2 f(n) \end{aligned} $$  for all positive integers $n$. Determine with proof the number of positive integers less than or equal to 1988 for which $f(n)=n$.
26. The overline in this problem will exclusively denote binary representation. We will show by induction that if \( n = \overline{c_k c_{k-1} \ldots c_0} = \sum_{i=0}^{k} c_i 2^i \) is the binary representation of \( n \left( c_i \in \{0,1\} \right) \), then \( f(n) = \overline{c_0 c_1 \ldots c_k} = \sum_{i=0}^{k} c_i 2^{k-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 = \overline{c_k c_{k-1} \ldots c_0} \). We observe three cases: (i) \( c_0 = 0 \Rightarrow n = 2m \Rightarrow f(n) = f(m) = \overline{0 c_1 \ldots c_k} = \overline{c_0 c_1 \ldots c_k} \). (ii) \( c_0 = 1, c_1 = 0 \Rightarrow n = 4m + 1 \Rightarrow f(n) = 2f(2m + 1) - f(m) = 2 \cdot \overline{1 c_2 \ldots c_k} - \overline{c_2 \ldots c_k} = 2^k + 2 \cdot \overline{c_2 \ldots c_k} - \overline{c_2 \ldots c_k} = \overline{10 c_2 \ldots c_k} = \overline{c_0 c_1 \ldots c_k} \). (iii) \( c_0 = 1, c_1 = 1 \Rightarrow n = 4m + 3 \Rightarrow f(n) = 3f(2m + 1) - 2f(m) = 3 \cdot \overline{1 c_2 \ldots c_k} - 2 \cdot \overline{c_2 \ldots c_k} = 2^k + 2^{k-1} + 3 \cdot \overline{c_2 \ldots c_k} - 2 \cdot \overline{c_2 \ldots c_k} = \overline{11 c_2 \ldots c_k} = \overline{c_0 c_1 \ldots c_k} \). We thus have to find the number of palindromes in binary representation smaller than \( 1998 = \overline{11111000100} \). We note that for all \( m \in \mathbb{N} \) the numbers of \( 2m \)- and \( (2m-1) \)-digit binary palindromes are both equal to \( 2^{m-1} \). We also note that \( \overline{11111011111} \) and \( \overline{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 \leq 1998 \) such that \( f(n) = n \) is thus equal to \( 1 + 1 + 2 + 2 + 4 + 4 + 8 + 8 + 16 + 16 + 32 - 2 = 92 \).