Maths Olympiad Prep

Library / /152 of 155

Algebra Difficulty 7.4 National olympiad, round 2 Prove it Saudi Arabia

A polynomial P(x)P(x) with integer coefficients is called cube-represented if it can be represented as the sum of several cubes of polynomials with integer coefficients.

Examples: 3x+3x23x + 3x^{2} is cube-represented because 3x+3x2=(x+1)3+(x)3+(1)33x + 3x^{2} = (x+1)^{3} + (-x)^{3} + (-1)^{3}.

1. Is 3x23x^{2} a cube-represented polynomial?

2. How many quadratic polynomials P(x)P(x) with integer coefficients belonging to the set {1,2,3,,2017}\{1,2,3, \ldots, 2017\} are cube-represented?

Solution

A polynomial with integer coefficients is called "nice" if the coefficients in the terms whose degree is not a multiple of 33, are multiples of 33, and their sum is a multiple of 66. Clearly, the sum of nice polynomials is a nice polynomial, and the sum of cube-represented polynomials is a cube-represented polynomial. We shall prove the following lemma:

Lemma. A polynomial is cube-represented if and only if it is nice.

Consider the cube of a polynomial P(x)P(x) with integer coefficients, where:
P(x)=anxn++a1x+a0 P(x) = a_{n} x^{n} + \cdots + a_{1} x + a_{0}
After expanding, all terms of P3(x)P^{3}(x) are either of the form ai3x3ia_{i}^{3} x^{3i}, or 3ai2ajx2i+j3 a_{i}^{2} a_{j} x^{2i + j} with ii different from jj, or of the form 6aiajakxi+j+k6 a_{i} a_{j} a_{k} x^{i + j + k} with i,j,ki, j, k distinct.

We have 32i+j3 \mid 2i + j if and only if 32j+i3 \mid 2j + i, and ai2aj+aj2ai=aiaj(ai+aj)a_{i}^{2} a_{j} + a_{j}^{2} a_{i} = a_{i} a_{j}(a_{i} + a_{j}) which is always an even number. From here, clearly a cube-represented polynomial has to be a nice polynomial, as defined above.

Second, consider a nice polynomial P(x)P(x). We will prove by induction on nn that P(x)P(x) is cube-represented, with nn being the integer such that the degree of P(x)P(x) does not exceed 3n3n, but is larger than 3n33n-3.

For the base case where n=1n=1, P(x)=a3x3+3a2x2+3a1x+a0P(x) = a_{3} x^{3} + 3a_{2} x^{2} + 3a_{1} x + a_{0}, where 2a1a22 \mid a_{1} - a_{2}.
We can write
P(x)=a1+a22(x+1)3+a1a22(x1)3+(a3a1)x3+(a0a2)13 P(x) = \frac{a_{1} + a_{2}}{2} (x+1)^{3} + \frac{a_{1} - a_{2}}{2} (x-1)^{3} + (a_{3} - a_{1}) x^{3} + (a_{0} - a_{2}) 1^{3}
which is obviously a cube-represented polynomial.

Assume the result is true for n1n-1. If P(x)=a3nx3n+3a3n1x3n1+3a3n2x3n2+Q(x)P(x) = a_{3n} x^{3n} + 3a_{3n-1} x^{3n-1} + 3a_{3n-2} x^{3n-2} + Q(x) is nice, where the degree of Q(x)Q(x) is at most 3n33n-3.

Then either a3n1+a3n2a_{3n-1} + a_{3n-2} is even and Q(x)Q(x) is good, or a3n1+a3n2a_{3n-1} + a_{3n-2} is odd, and Q(x)3x3n4Q(x) - 3x^{3n-4} is good.

In the first case
P(x)=a3n1+a3n22(xn+xn1)3+a3n2a3n12(xnxn1)3+(a3na3n2)x3n+Q(x)a2(xn1)3 \begin{aligned} & P(x) = \frac{a_{3n-1} + a_{3n-2}}{2} (x^{n} + x^{n-1})^{3} + \frac{a_{3n-2} - a_{3n-1}}{2} (x^{n} - x^{n-1})^{3} + \\ & (a_{3n} - a_{3n-2}) x^{3n} + Q(x) - a_{2} (x^{n-1})^{3} \end{aligned}

In the second case
P(x)=a3n1+a3n212(xn+xn1)3+a3n2a3n112(xnxn1)3+(xn+xn2)3+(a3na3n2)x3n+(Q(x)3x3n4)a2x3n3 \begin{aligned} P(x) &= \frac{a_{3n-1} + a_{3n-2} - 1}{2} (x^{n} + x^{n-1})^{3} + \frac{a_{3n-2} - a_{3n-1} - 1}{2} (x^{n} - x^{n-1})^{3} \\ & + (x^{n} + x^{n-2})^{3} + (a_{3n} - a_{3n-2}) x^{3n} + (Q(x) - 3x^{3n-4}) - a_{2} x^{3n-3} \end{aligned}
so in both cases, we have P(x)P(x) is a nice polynomial. Our lemma has been proved.

Back to our problem,

1. With the lemma, we can easily verify that P(x)=3x2P(x) = 3x^{2} is not a nice polynomial, so it cannot be a cube-represented polynomial.

2. We need to count the number of triples (a,b,c)(a, b, c) which belong to the set {1,2,,2017}\{1,2, \ldots, 2017\} such that P(x)=ax2+bx+cP(x) = a x^{2} + b x + c is cube-represented, that is, it's nice.

P(x)P(x) is nice if and only if a,ba, b are multiples of 33 and a+ba + b is a multiple of 22.

We have a,b{3,6,,2016}a, b \in \{3, 6, \ldots, 2016\} and a+ba + b is even, there are 3362336^{2} such pairs. Value cc can be arbitrary, so the number of triples (a,b,c)(a, b, c) is 201733622017 \cdot 336^{2}, which is the number of quadratic cube-represented polynomials satisfying the problem.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.