Olympiad Maths Prep

Library / /28 of 45

Algebra Difficulty 6.4 National olympiad Prove it Ukraine

Let P(x)P(x), Q(x)Q(x) and R(x)R(x) be polynomials with integer coefficients, such that the equality holds: P(x)=Q(x)R(x)P(x) = Q(x)R(x). We denote by aa and bb the maximum of the absolute values of coefficients of the polynomials P(x)P(x) and Q(x)Q(x) respectively. Does the condition b2023ab \le 2023a always hold?

Solution

Answer: No, not necessarily.

As an example, consider the following two polynomials:

Q(x)=1+2x+3x2+4x3++2023x2022+2024x2023+2023x2024++x4046,R(x)=x1, Q(x) = 1 + 2x + 3x^2 + 4x^3 + \cdots + 2023x^{2022} + 2024x^{2023} + 2023x^{2024} + \cdots + x^{4046}, \quad R(x) = x - 1,
then P(x)=Q(x)(x1)=1xx2x2023+x2024+x2025++x4047. \text{then } P(x) = Q(x)(x-1) = -1 - x - x^2 - \cdots - x^{2023} + x^{2024} + x^{2025} + \cdots + x^{4047}.
Then a=1a = 1 and b=2024b = 2024, with b>2023ab > 2023a.

Alternative solution. Consider the following two polynomials:
P(x)=(x31)N,Q(x)=(x2+x+1)N. P(x) = (x^3 - 1)^N, \quad Q(x) = (x^2 + x + 1)^N.
By the construction of P(x):Q(x)P(x) : Q(x), that is, the polynomial R(x)R(x) exists. Since
P(x)=(x31)N=j=0NCNjx3ja=CNj for some j=0,Na=CNj<j=0NCNj=(1+1)N=2N. P(x) = (x^3 - 1)^N = \sum_{j=0}^{N} C_N^j x^{3j} \Rightarrow a = C_N^j \text{ for some } j = 0, N \Rightarrow a = C_N^j < \sum_{j=0}^{N} C_N^j = (1+1)^N = 2^N.
The sum of the coefficients of the polynomial Q(x)Q(x) is equal to Q(1)=(1+1+1)N=3NQ(1) = (1 + 1 + 1)^N = 3^N and the number of coefficients is 2N+12N + 1, because it has degree 2N2N. Therefore, according to Dirichlet's principle, there is a coefficient at least
3N2N+1b3N2N+1. \frac{3^N}{2N + 1} \Rightarrow b \ge \frac{3^N}{2N + 1}.
It is clear that with sufficiently large NN inequality will hold:
ba3N2N(2N+1)>2023. \frac{b}{a} \ge \frac{3^N}{2^N(2N + 1)} > 2023.

Looking for a route rather than 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.