IMO 1994- Problem 3

Problem: For any positive integer $k$, let $f(k)$ be the number of elements in the set $\left\{k+1,k+2,...,2k\right\}$ 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$.
Solution: Let $g(k)$ denote the number of elements in the set $\left\{1,...,n\right\}$ whose binary representation has exactly three ones. Then $f(k)$ and $g(k)$ are both increasing and $f(k)=g(2k)-g(k)$. Hence
   $f(k+1)-f(k)=g(2k+2)-g(k+1)-g(2k)+g(k)=g(2k+2)-g(2k)-[g(k+1)-g(k)]$
Since either both $2k+2$ is counted in $g(2k+2)$ and $k+1$ is counted in $g(k+1)$ or neither is. Thus $f(k+1)-f(k)$ is either $1$ or $0$ depending on where $2k+1$ is counted in $g(2k+1)$ or not. Since $f(2^n)=C_{n+1}^3-C_{n}^3=C_{n}^2$, the image of $f$ is $\mathbb{N}\cup \left\{0\right\}$. This proves (a)
.
Let $m$ be any positive integer for which there is only one $k$ with $f(k)=m$. Then $f(k+1)-f(k)=1=f(k)-f(k-1)$.
The former means $2k+1$ is counted in $g(2k+2)$, or equivalently, the binary representation of $k$ has exactly two ones. The same holds for $k-1$. This happens only when the last two digits of $k-1$ are $01$. In other words, $k=2^n+2$. But
$f(2^n+2)=g(2^{n+1}+4)-g(2^n+2)=1+g(2^{n+1})-g(2^n)=1+C_{n}^2$
Thus the answer is any number of the form $1+C_{n}^2,n\ge 2$.
Source: http://sms.math.nus.edu.sg/simo/IMO_Problems/94.pdf