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

Hint: Determine $f(k)$ between two consective powers of $2$.

  Solution