IMO 1985/A3 solution

IMO 1985

Problem A3

For any polynomial P(x) = a₀ + a₁x + ... + a_kx^k with integer coefficients, the number of odd coefficients is denoted by o(P). For i = 0, 1, 2, ... let Q_i(x) = (1 + x)ⁱ. Prove that if i₁, i₂, ... , i_n are integers satisfying 0 ≤ i₁ < i₂ < ... < i_n, then:

o(Q_i₁ + Q_i₂ + ... + Q_{i_n}) ≥ o(Q_i₁).

Solution

If i is a power of 2, then all coefficients of Q_i are even except the first and last. [There are various ways to prove this. Let iCr denote the rth coefficient, so iCr = i!/(r!(i-r)!). Suppose 0 < r < i. Then iCr = i-1Cr-1 i/r, but i-1Cr-1 is an integer and i is divisible by a higher power of 2 than r, hence iCr is even.]

Let Q = Q_i₁ + ... + Q_{i_n}. We use induction on i_n. If i_n = 1, then we must have n = 2, i₁ = 0, and i₂ = 1, so Q = 2 + x, which has the same number of odd coefficients as Q_i₁ = 1. So suppose it is true for smaller values of i_n. Take m a power of 2 so that m ≤ i_n < 2m. We consider two cases i₁ ≥ m and i₁ < m.

Consider first i₁ ≥ m. Then Q_i₁ = (1 + x)^mA, Q = (1 + x)^mB, where A and B have degree less than m. Moreover, A and B are of the same form as Q_i₁ and Q, (all the i_js are reduced by m, so we have o(A) ≤ o(B) by induction. Also o(Q_i₁) = o((1 + x)^mA) = o(A + x^mA) = 2o(A) ≤ 2o(B) = o(B + x^mB) = o((1 + x)^mB) = o(Q), which establishes the result for i_n.

It remains to consider the case i₁ < m. Take r so that i_r < m, i_r+1 > m. Set A = Q_i₁ + ... + Q_{i_r}, (1 + x)^mB = Q_{i_r+1} + ... + Q_{i_n}, so that A and B have degree < m. Then o(Q) = o(A + (1 + x)^mB) = o(A + B + x^mB) = o(A + B) + o(B). Now o(A - B) + o(B) >= o(A - B + B) = o(A), because a coefficient of A is only odd if just one of the corresponding coefficients of A - B and B is odd. But o(A - B) = o(A + B), because corresponding coefficients of A - B and A + B are either equal or of the same parity. Hence o(A + B) + o(B) ≥ o(A). But o(A) ≥ o(Q_{i_i}) by induction. So we have established the result for i_n.

Solutions are also available in Murray S Klamkin, International Mathematical Olympiads 1978-1985, MAA 1986, and in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.

26th IMO 1985