1985 IMO Problems/Problem 3

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 $w(P)$ . For $i = 0, 1, \ldots$ , let $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

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

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

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

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

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

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

1985 IMO (Problems)
Preceded by Problem 2	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 4