# 1985 IMO Problems/Problem 3

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

## Problem

For any polynomial $P(x) = a_0 + a_1 x + \cdots + a_k x^k$ with integer coefficients, the number of coefficients which are odd is denoted by $\displaystyle w(P)$. For $i = 0, 1, \ldots$, let $\displaystyle Q_i (x) = (1+x)^i$. Prove that if $i_1, i_2, \ldots , i_n$ are integers such that $0 \leq i_1 < i_2 < \cdots < i_n$, then

$\displaystyle w(Q_{i_1} + Q_{i_2} + \cdots + Q_{i_n}) \ge w(Q_{i_1})$.

## Solution

We first observe that $(1+x)^{2^m} \equiv 1 + x^{2^m} \pmod{2}$, so for any polynomial $\displaystyle P$ of degree less than $\displaystyle 2^m$, $w(P\cdot Q_{2^m}) = 2w (P)$.

Let $\displaystyle k$ be the largest power of 2 that is less than or equal to $\displaystyle i_n$. We proceed by induction on $\displaystyle k$.

For $\displaystyle k = 0$, the problem is trivial.

Now assume that the problem holds for $\displaystyle k-1$. We now have two cases: $i_1 \ge k$, and $\displaystyle i_1 < k$.

In the first case, we note that $w \left( \sum_{j=1}^{n}Q_{i_j} \right) = w \left( (1+x)^k \sum_{j=1}^{n}Q_{i_j - k} \right) = 2 w \left( \sum_{j=1}^{n}Q_{i_j - k} \right)$, which is greater than or equal to $w( Q_{i_1} )$ by assumption.

In the second case, we use the division algorithm to note that

$\sum_{j=1}^{n}Q_{i_j} = \sum_{j=0}^{k-1}a_j x^j + (1+x)^k \sum_{j=0}^{k-1} b_j x^j \equiv \sum_{j=0}^{k-1}\left[ (a_j + b_j)x^j + b_j x^{j+k} \right] \pmod{2}$.

But by assumption, $w \left( \sum_{j=0}^{k-1}a_j x^j \right) \ge w( Q_{i_1})$, and for each odd $\displaystyle a_j$, at least one of $\displaystyle (a_j + b_j )$ and $\displaystyle b_j$ must be odd, Q.E.D.