IMO 1994 · Problem 3

For any positive integer \(k\), let \(f(k)\) be the number of elements in the set \(\{k+1,k+2,\ldots,2k\}\) whose base 2 representation has precisely three 1s.

  • (a) Prove that, for each positive integer \(m\), there exists at least one positive integer \(k\) such that \(f(k)=m\).
  • (b) Determine all positive integers \(m\) for which there exists exactly one \(k\) with \(f(k)=m\).

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

Answer

The positive integers in part (b) are exactly \[ \boxed{m=1+\binom r2\qquad(r=2,3,4,\ldots).} \] For each such \(m\), the unique corresponding integer is \(k=2^r+2\).

Solution

Let \(s(n)\) denote the number of 1s in the binary representation of \(n\). We first prove that \[ f(k+1)-f(k)= \begin{cases} 1,&s(k)=2,\\ 0,&s(k)\ne2. \end{cases} \tag{1} \]

Indeed, passing from the set \(\{k+1,\ldots,2k\}\) to \(\{k+2,\ldots,2k+2\}\) removes \(k+1\) and adds \(2k+1\) and \(2k+2\). Since \[ s(2k+2)=s(k+1), \] the contributions of \(k+1\) and \(2k+2\) cancel. Moreover, \[ s(2k+1)=s(k)+1, \] so the remaining contribution is 1 precisely when \(s(k)=2\). This proves (1).

Since \(f(1)=0\), summing (1) gives \[ \boxed{f(k)=\#\{n:1\le n<k,\ s(n)=2\}.} \tag{2} \]

Part (a). List the positive integers having exactly two binary 1s in increasing order: \[ a_1<a_2<a_3<\cdots. \] This sequence is infinite, since it contains \(2^r+1\) for every integer \(r\ge1\). By (2), for every positive integer \(m\), \[ f(a_m+1)=m. \] Thus every positive integer \(m\) is attained.

Part (b). Formula (2) shows that \[ f(k)=m \quad\Longleftrightarrow\quad a_m<k\le a_{m+1}. \] Consequently, the number of integers \(k\) satisfying \(f(k)=m\) is \(a_{m+1}-a_m\). There is exactly one such \(k\) if and only if \[ a_{m+1}=a_m+1. \tag{3} \]

We therefore determine when two consecutive integers both have exactly two binary 1s. Suppose \(s(n)=s(n+1)=2\).

If \(n\) is even, adding 1 changes its final binary digit from 0 to 1 without affecting any other digit. This gives \(s(n+1)=3\), a contradiction. Hence \(n\) is odd. Since \(s(n)=2\), it follows that \[ n=2^r+1 \] for some integer \(r\ge1\). If \(r=1\), then \(n+1=4\) has only one binary 1. If \(r\ge2\), however, \[ n+1=2^r+2 \] has exactly two binary 1s. Thus all such consecutive pairs are precisely \[ (2^r+1,\ 2^r+2),\qquad r\ge2. \tag{4} \]

There are exactly \(\binom r2\) positive integers below \(2^r\) with two binary 1s: their two occupied positions can be chosen arbitrarily from positions \(0,1,\ldots,r-1\). The smallest integer at least \(2^r\) with two binary 1s is \(2^r+1\). Therefore \[ a_{\binom r2+1}=2^r+1. \] Together with (3) and (4), this proves that uniqueness holds exactly for \[ m=\binom r2+1,\qquad r\ge2, \] and the unique integer is \(k=a_m+1=2^r+2\).

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