33rd IMO shortlist 1992/17 solution

33rd IMO 1992 shortlist

Problem 17

Let b(n) be the number of 1s in the binary representation of a positive integer n. Show that b(n²) ≤ b(n) (b(n) + 1)/2 with equality for infinitely many positive integers n. Show that there is a sequence of positive integers a₁ < a₂ < a₃ < ... such that b(a_n²)/b(a_n) tends to zero.

Solution

Consider N' = 2ⁿ + N in binary. If N has a 0 in the 2ⁿ position, then this changes to a 1 in N' and so b(N') = b(N) + 1. If not, then N has 0 followed by r 1s, the last in the 2ⁿ position. Adding 2ⁿ changes the 0 to 1 and the r 1s to 0s, so b(N') < b(N) + 1. Thus in any case b(N') < b(N) + 1. Now we can get M + N by adding b(M) powers of 2 to N, so b(M+N) ≤ b(M) + b(N).

We now show that b(n²) ≤ b(n) (b(n) + 1)/2 by induction on n. For n = 1, it is obvious. Suppose it is true for < N. If N is even, then b(N²) = b(N²/4) ≤ ½ b(N/2) (b(N/2) + 1) = ½ b(N) (b(N) + 1). So suppose N is odd = 2n+1. Then b(N²) = b(4n²+4n+1) = b(n²+n) + 1 ≤ b(n²) + b(n) + 1 ≤ ½ b(n) (b(n) + 1) + b(n) + 1 = ½ (b(n) + 1)(b(n) + 2) = ½ b(N) (b(N) + 1). So the result is true for N.

Put N = 2^2¹ + 2^2² + 2^2³ + ... + 2^{2^m}. If we consider N², there are m terms 2^2ⁱ2^2ⁱ = 2^2ⁱ⁺¹ and ½m(m-1) terms 2 2^2ⁱ 2^{2^j} = 2^{2ⁱ+2^j+1} with i ≠ j. Evidently these are all distinct, so b(N) = m and b(N²) = ½m(m+1) = ½ b(N) (b(N)+1).

Put N = 2^{2^m-1} - 2^{2^m-2¹} - 2^{2^m-2²} - 2^{2^m-2³} - ... - 2^{2^m-2^m-1} - 1. Note that 2^{2^m-1} - 1 has 2^m 1s (and no 0s) in binary. We are subtracting m-1 smaller distinct powers of 2, so b(N) = 2^m - m + 1. Now consider N². We get m+1 positive powers of 2 from squaring each term. We get m negative terms: 2 x first term x other term. But these cancel with m of the first set to leave 1. We then get ½m(m-1) positive terms, all different, from 2 x other term x different other term. Hence b(N²) = ½m(m-1) + 1. Hence b(N²)/b(N) → 0.

33rd IMO shortlist 1992