IMO 1988 · Problem 3

A function \(f\) is defined on the positive integers by \[ \begin{aligned} f(1)&=1,\quad f(3)=3,\\ f(2n)&=f(n),\\ f(4n+1)&=2f(2n+1)-f(n),\\ f(4n+3)&=3f(2n+1)-2f(n), \end{aligned} \] for all positive integers \(n\).

Determine the number of positive integers \(n\), less than or equal to 1988, for which \(f(n)=n\).

Official text of the problem. Official problem paper (PDF)

Answer

\[ \boxed{92} \]

Solution

Let \(r(n)\) be the integer obtained by reversing the binary digits of \(n\), discarding any leading zeros in the reversed string. We first prove that \[ f(n)=r(n) \] for every positive integer \(n\).

Suppose \(n\) has \(\ell\) binary digits. Multiplication by \(2\) appends a zero, so \[ r(2n)=r(n). \] Similarly, the binary representations of \(2n+1\), \(4n+1\), and \(4n+3\) are obtained by appending \(1\), \(01\), and \(11\), respectively. Reversing these strings gives \[ \begin{aligned} r(2n+1)&=2^\ell+r(n),\\ r(4n+1)&=2^{\ell+1}+r(n) =2r(2n+1)-r(n),\\ r(4n+3)&=3\cdot2^\ell+r(n) =3r(2n+1)-2r(n). \end{aligned} \] Also, \(r(1)=1\) and \(r(3)=3\). Thus \(r\) satisfies all the defining relations for \(f\).

These relations determine the function uniquely by strong induction: every even argument reduces to a smaller positive argument, and every odd argument other than \(1\) and \(3\) has the form \(4n+1\) or \(4n+3\) with \(n\ge1\), whose corresponding right-hand arguments are smaller. Consequently, \(f(n)=r(n)\) for all positive integers \(n\).

The last digit of the reversed binary string is always \(1\), so \(r(n)\) is odd. Hence an integer satisfying \(r(n)=n\) must be odd. For odd \(n\), reversal preserves the number of binary digits, and uniqueness of binary representation shows that \(r(n)=n\) exactly when its binary representation is a palindrome.

It remains to count binary palindromes at most \(1988\). A palindrome with \(\ell\) binary digits is determined by its first \(\lceil\ell/2\rceil\) digits. The first digit must be \(1\), and the others can be chosen freely, giving \[ 2^{\lceil\ell/2\rceil-1} \] such palindromes. Since \(2^{10}\le1988<2^{11}\), we first count all palindromes with at most eleven digits: \[ \sum_{\ell=1}^{11}2^{\lceil\ell/2\rceil-1} =2(1+2+4+8+16)+32 =94. \]

We now remove those exceeding \(1988\). Any eleven-digit binary number whose first five digits are not all \(1\) is at most \[ (11110111111)_2=1983. \] Thus a palindrome exceeding \(1988\) must begin with five ones and, by symmetry, end with five ones. Its only undetermined digit is the middle digit, so the only possibilities are \[ (11111011111)_2=2015, \qquad (11111111111)_2=2047. \] Both exceed \(1988\). Therefore the required number is \[ 94-2=\boxed{92}. \]

The solution was checked against John Scholes' IMO solution archive (Kalva).