IMO 1992 SL 17

Origin: SWE

Problem

Let \alpha(n) be the number of digits equal to one in the binary representation of a positive integer n. Prove that: (a) the inequality \alpha(n2) \leq1 2\alpha(n)(\alpha(n) + 1) holds; (b) the above inequality is an equality for infinitely many positive integers; (c) there exists a sequence (ni)\infty 1 such that \alpha(n2 i )/\alpha(ni) \to0 as i \to\infty. Alternative parts: Prove that there exists a sequence (ni)\infty such that \alpha(n2 i )/\alpha(ni) tends to (d) \infty; (e) an arbitrary real number \gamma \in(0, 1); (f) an arbitrary real number \gamma \geq0.

Solution

(a) Let n = k i=1 2ai, so that \alpha(n) = k. Then n2 =  i 22ai +  i<j 2ai+aj+1 has at most k +
k  = k(k+1) binary ones. (b) The above inequality is an equality for all numbers nk = 2k. (c) Put nm = 22m−1 −m j=1 22m−2j, where m > 1. It is easy to see that \alpha(nm) = 2m −m. On the other hand, squaring and simplifying yields n2 m = 1 +  i<j 22m+1+1−2i−2j. Hence \alpha(n2 m) = 1 + m(m+1) and thus \alpha(n2 m) \alpha(nm) = 2 + m(m + 1) 2(2m −m) \to0 as m \to\infty. Solution to the alternative parts. (1) Let n = n i=1 22i. Then n2 = n i=1 22i+1 +  i<j 22i+2j+1 has exactly k(k+1) binary ones, and therefore \alpha(n2) \alpha(n) = 2k k(k+1) \to\infty. (2) Consider the sequence ni constructed in part (c). Let \theta > 1 be a constant to be chosen later, and let Ni = 2mini −1 where mi > \alpha(ni) is such that mi/\alpha(ni) \to\theta as i \to\infty. Then \alpha(Ni) = \alpha(ni) + mi −1, whereas N 2 i = 22min2 i −2mi+1ni +1 and \alpha(N 2 i ) = \alpha(n2 i )−\alpha(ni)+mi. It follows that lim i\to\infty \alpha(N 2 i ) \alpha(Ni) = lim i\to\infty \alpha(n2 i ) + (\theta −1)\alpha(ni) (1 + \theta)\alpha(ni) = \theta −1 \theta + 1, which is equal to \gamma \in[0, 1] for \theta = 1+\gamma 1−\gamma (for \gamma = 1 we set mi/\alpha(ni) \to \infty). (3) Let be given a sequence (ni)\infty i=1 with \alpha(n2 i )/\alpha(ni) \to\gamma. Taking mi > \alpha(ni) and Ni = 2mini + 1 we easily find that \alpha(Ni) = \alpha(ni) + 1 and \alpha(N 2 i ) = \alpha(n2 i ) + \alpha(ni) + 1. Hence \alpha(N 2 i )/\alpha(Ni) = \gamma + 1. Continuing this procedure we can construct a sequence ti such that \alpha(t2 i )/\alpha(ti) = \gamma + k for an arbitrary k \inN.