IMO 1988 SL 2

Origin: BUL

Problem

Let n be a positive integer. Find the number of odd coefficients of the polynomial un(x) = (x2 + x + 1)n.

Solution

For polynomials f(x), g(x) with integer coefficients, we use the notation f(x) ∼g(x) if all the coefficients of f −g are even. Let n = 2s. It is immediately shown by induction that (x2 + x + 1)2s ∼x2s+1 + x2s + 1, and the required number for n = 2s is 3.

Let n = 2s −1. If s is odd, then n \equiv1 (mod 3), while for s even, n \equiv0 (mod 3). Consider the polynomial Rs(x) = ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ (x + 1)(x2n−1 + x2n−4 + \cdot \cdot \cdot + xn+3) + xn+1 +xn + xn−1 + (x + 1)(xn−4 + xn−7 + \cdot \cdot \cdot + 1), 2 ∤s; (x + 1)(x2n−1 + x2n−4 + \cdot \cdot \cdot + xn+2) + xn +(x + 1)(xn−3 + xn−6 + \cdot \cdot \cdot + 1), 2 | s. It is easily checked that (x2+x+1)Rs(x) ∼x2s+1 +x2s +1 ∼(x2+x+1)2s, so that Rs(x) ∼(x2+x+1)2s−1. In this case, the number of odd coefficients is (2s+2 −(−1)s)/3. Now we pass to the general case. Let the number n be represented in the binary system as n = 11 . . . 1    ak 00 . . .0    bk 11 . . .1    ak−1 00 . . .0    bk−1 . . . 11 . . . 1    a1 00 . . . 0    b1 , bi > 0 (i > 1), b1 \geq0, and ai > 0. Then n = k i=1 2si(2ai −1), where si = b1 + a1 + b2 + a2 + \cdot \cdot \cdot + bi, and hence un(x) = (x2 + x + 1)n = k

i=1 (x2 + x + 1)2si(2ai −1) ∼ k

i=1 Rai(x2si ). Let Rai(x2si ) ∼xri,1 + \cdot \cdot \cdot + xri,di ; clearly ri,j is divisible by 2si and ri,j \leq2si+1(2ai −1) < 2si+1, so that for any j, ri,j can have nonzero binary digits only in some position t, si \leqt \leqsi+1 −1. Therefore, in k

i=1 Rai(x2si ) ∼ k

i=1 (xri,1 + \cdot \cdot \cdot + xri,di ) = k  i=1 di  pi=1 xr1,p1 +r2,p2+\cdot\cdot\cdot+rk,pk all the exponents r1,p1 +r2,p2 +\cdot \cdot \cdot+rk,pk are different, so that the number of odd coefficients in un(x) is k

i=1 di = k

i=1 2ai+2 −(−1)ai .