MathDB

17

Part of 1992 IMO Shortlist

Problems(1)

Number of digits equal to one in the binary representation

Source: IMO Shortlist 1992, Problem 17

8/13/2008
Let α(n) \alpha(n) be the number of digits equal to one in the binary representation of a positive integer n. n. Prove that: (a) the inequality α(n)(n2)≤12α(n)(α(n)+1) \alpha(n) (n^2 ) \leq \frac{1}{2} \alpha(n)(\alpha(n) + 1) holds; (b) the above inequality is an equality for infinitely many positive integers, and (c) there exists a sequence (ni)1∞ (n_i )^{\infty}_1 such that α(ni2)α(ni \frac{\alpha ( n^2_i )}{\alpha (n_i } goes to zero as i i goes to ∞. \infty. Alternative problem: Prove that there exists a sequence a sequence (ni)1∞ (n_i )^{\infty}_1 such that α(ni2)α(ni) \frac{\alpha ( n^2_i )}{\alpha (n_i )} (d) ∞; \infty; (e) an arbitrary real number γ∈(0,1) \gamma \in (0,1); (f) an arbitrary real number γ≥0 \gamma \geq 0; as i i goes to ∞. \infty.
inequalitiesalgebraDigitsbinary representationcombinatoricsSequenceIMO Shortlist