IMO 1985 · Problem 3

For any polynomial \(P(x)=a_0+a_1x+\cdots+a_kx^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\le i_1<i_2<\cdots<i_n\), then \[ w(Q_{i_1}+Q_{i_2}+\cdots+Q_{i_n})\ge w(Q_{i_1}). \]

Official text of the problem. Official problem paper (PDF)

Solution

Reduce all coefficients modulo \(2\). We may therefore work in \(\mathbb F_2[x]\), where \(w(F)\) counts the nonzero coefficients of \(F\). This does not change any weight in the desired inequality.

For any two polynomials \(F,G\), \[ w(F+G)\le w(F)+w(G), \] because every nonzero coefficient of \(F+G\) comes from a nonzero coefficient of at least one summand.

Since \((1+x)^2=1+x^2\) in \(\mathbb F_2[x]\), we have \[ Q_{2r}(x)=Q_r(x^2),\qquad Q_{2r+1}(x)=(1+x)Q_r(x^2). \] The even and odd powers in the second expression have disjoint supports, so \[ w(Q_{2r})=w(Q_r),\qquad w(Q_{2r+1})=2w(Q_r). \tag{1} \]

We prove the assertion by strong induction on the smallest index \(m=i_1\), allowing any finite nonempty list of distinct indices with that minimum.

If \(m=0\), the sum is nonzero: its highest-degree term comes only from \(Q_{i_n}\) and has coefficient \(1\). Thus its weight is at least \(1=w(Q_0)\).

Now let \(m>0\), and assume the assertion for every smaller minimum. Put \[ A(x)=\sum_{\substack{1\le j\le n\\ i_j\text{ even}}}Q_{i_j/2}(x), \qquad B(x)=\sum_{\substack{1\le j\le n\\ i_j\text{ odd}}}Q_{(i_j-1)/2}(x), \] with an empty sum understood as zero. Writing \(S=\sum_{j=1}^nQ_{i_j}\), we obtain \[ S(x)=A(x^2)+(1+x)B(x^2) =(A+B)(x^2)+xB(x^2). \] The two terms on the right contain only even and odd powers, respectively. Hence \[ w(S)=w(A+B)+w(B). \tag{2} \]

If \(m=2r\), then \(A\) is a sum of distinct \(Q_j\)'s with smallest index \(r<m\). The induction hypothesis gives \(w(A)\ge w(Q_r)\). Since \(A=(A+B)+B\), equations (1) and (2) yield \[ w(S)=w(A+B)+w(B)\ge w(A)\ge w(Q_r)=w(Q_m). \]

If \(m=2r+1\), then \(B\) contains \(Q_r\), and every other summand of \(A\) or \(B\) has index greater than \(r\). After cancelling repeated summands modulo \(2\), both \(B\) and \(A+B\) are therefore sums of distinct \(Q_j\)'s with smallest index \(r<m\). Applying the induction hypothesis to each gives \[ w(B)\ge w(Q_r),\qquad w(A+B)\ge w(Q_r). \] Consequently, by (1) and (2), \[ w(S)\ge 2w(Q_r)=w(Q_m). \]

Both cases establish the induction and prove the required inequality. \(\square\)

The solution was checked against John Scholes' IMO solution archive (Kalva).