IMO 1985 SL 3
Origin: NET
Problem
The weight w(p) of a polynomial p, p(x) = n i=0 aixi, with integer coefficients ai is defined as the number of its odd coefficients. For i = 0, 1, 2, . . ., let qi(x) = (1 + x)i. Prove that for any finite sequence 0 \leqi1 < i2 < \cdot \cdot \cdot < in, the inequality w(qi1 + \cdot \cdot \cdot + qin) \geqw(qi1) holds.
Solution
From the isosceles triangles AEF and FAE′ we obtain finally, with ∡EFA = \alpha, y 2x = cos \alpha = 1 −2 sin2(\alpha/2), x/(2x \sqrt 3) = sin(\alpha/2), and y/x = 5/3. 3. We shall write P \equivQ for two polynomials P and Q if P(x) −Q(x) has even coefficients. We observe that (1 + x)2m \equiv1 + x2m for every m \inN. Consequently, for every polynomial p with degree less than k = 2m, w(p \cdot qk) = 2w(p). Now we prove the inequality from the problem by induction on in. If in \leq1, the inequality is trivial. Assume it is true for any sequence with i1 < \cdot \cdot \cdot < in < 2m (m \geq1), and let there be given a sequence with k = 2m \leqin < 2m+1. Consider two cases. (i) i1 \geqk. Then w(qi1 +\cdot \cdot \cdot+qin) = 2w(qi1−k+\cdot \cdot \cdot+qin−k) \geq2w(qi1−k) = w(qi1). (ii) i1 < k. Then the polynomial p = qi1 + \cdot \cdot \cdot + qin has the form p = k−1 i=0 aixi + (1 + x)k k−1 i=0 bixi \equiv k−1 i=0 / (ai + bi)xi + bixi+k0 . Whenever some ai is odd, either ai + bi or bi in the above sum will be odd. It follows that w(p) \geqw(qi1), as claimed.
The proof is complete.