MathDB

2

Part of 2015 IMC

Problems(1)

IMC2015, problem 2

Source: IMC2015

7/29/2015
For a positive integer nn, let f(n)f(n) be the number obtained by writing nn in binary and replacing every 0 with 1 and vice versa. For example, n=23n=23 is 10111 in binary, so f(n)f(n) is 1000 in binary, therefore f(23)=8f(23) =8. Prove that ∑k=1nf(k)≤n24.\sum_{k=1}^n f(k) \leq \frac{n^2}{4}. When does equality hold?
(Proposed by Stephan Wagner, Stellenbosch University)
numberscollege contestsinequalitiesIMC2015