IMC 2015 · Day 1 · P2

If $r$ and $k$ are positive integers with $2^{r-1} \le k < 2^r$ then $k$ has $r$ binary digits, so $k + f(k) = \underbrace{11\dots1}_{r}{}_{(2)} = 2^r - 1$.

Assume that $2^{s-1} - 1 \le n \le 2^s - 1$. Then $$\begin{align*} \frac{n(n+1)}{2} + \sum_{k=1}^{n} f(k) &= \sum_{k=1}^{n} (k + f(k)) = \\ &= \sum_{r=1}^{s-1} \sum_{2^{r-1} \le k < 2^r} (k + f(k)) + \sum_{2^{s-1} \le k \le n} (k + f(k)) = \\ &= \sum_{r=1}^{s-1} 2^{r-1} \cdot (2^r - 1) + (n - 2^{s-1} + 1) \cdot (2^s - 1) = \\ &= \sum_{r=1}^{s-1} 2^{2r-1} - \sum_{r=1}^{s-1} 2^{r-1} + (n - 2^{s-1} + 1)(2^s - 1) = \\ &= \frac{2}{3} (4^{s-1} - 1) - (2^{s-1} - 1) + (2^s - 1) n - 2^{2s-1} + 3 \cdot 2^{s-1} - 1 = \\ &= (2^s - 1) n - \frac{1}{3} 4^s + 2^s - \frac{2}{3} \end{align*}$$ and therefore $$\begin{align*} \frac{n^2}{4} - \sum_{k=1}^{n} f(k) &= \frac{n^2}{4} - \left( (2^s - 1) n - \frac{1}{3} 4^s + 2^s - \frac{2}{3} - \frac{n(n+1)}{2} \right) = \\ &= \frac{3}{4} n^2 - \left( 2^s - \frac{3}{2} \right) n + \frac{1}{3} 4^s - 2^s + \frac{2}{3} = \\ &= \frac{3}{4} \left( n - \frac{2^{s+1} - 2}{3} \right) \left( n - \frac{2^{s+1} - 4}{3} \right). \end{align*}$$ Notice that the difference of the last two factors is less than 1, and one of them must be an integer: $\frac{2^{s+1}-2}{3}$ is integer if $s$ is even, and $\frac{2^{s+1}-4}{3}$ is integer if $s$ is odd. Therefore, either one of them is 0, resulting a zero product, or both factors have the same sign, so the product is strictly positive. This solves the problem and shows that equality occurs if $n = \frac{2^{s+1}-2}{3}$ ($s$ is even) or $n = \frac{2^{s+1}-4}{3}$ ($s$ is odd).