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
k=1∑nf(k)≤4n2.
When does equality hold?
Original from the official PDF
This transcription was compared symbol by symbol with the original, but not yet by a person.
Time on this problem
Work for at least 45 minutes before opening the solution.
Official solution
(Proposed by Stephan Wagner, Stellenbosch University)
Solution. If r and k are positive integers with 2r−1≤k<2r then k has r binary digits, so k+f(k)=(2)11…1=2r−1.
Notice that the difference of the last two factors is less than 1, and one of them must be an integer: 32s+1−2 is integer if s is even, and 32s+1−4 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=32s+1−2 (s is even) or n=32s+1−4 (s is odd).
Transcribed from the official solutions, pages 2–3. This transcription has not been checked a second time; if in doubt, look at the original.
Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.