International Mathematics Competition
for University Students
2015

IMC2015: Day 1, Problem 2

2. For a positive integer $n$, let $f(n)$ be the number obtained by writing $n$ in binary and replacing every 0 with 1 and vice versa. For example, $n=23$ is 10111 in binary, so $f(n)$ is 1000 in binary, therefore $f(23) =8$. Prove that \[\sum_{k=1}^n f(k) \leq \frac{n^2}{4}.\] When does equality hold?

Proposed by Stephan Wagner, Stellenbosch University

Assume that $2^{s-1}-1\le n\le 2^s-1$. Then \[ \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) = \] \[ = \tfrac23(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 - \tfrac134^s + 2^s -\tfrac23 \] and therefore \[ \frac{n^2}4 - \sum_{k=1}^n f(k) = \frac{n^2}4 -\left( (2^s-1)n - \tfrac134^s + 2^s -\tfrac23 - \frac{n(n+1)}2 \right) = \] \[ = \tfrac34 n^2 - (2^s-\tfrac32)n + \tfrac13 4^s -2^s +\tfrac23 =\] \[ = \frac34 \left(n-\frac{2^{s+1}-2}3\right) \left(n-\frac{2^{s+1}-4}3\right). \] 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=\dfrac{2^{s+1}-2}3$ ($s$ is even) or $n=\dfrac{2^{s+1}-4}3$ ($s$ is odd).