Maths Olympiad Prep

Library / /32 of 53

Algebra Difficulty 6.8 National olympiad Prove it Vietnam

Consider 2 non-constant polynomials P(x),Q(x)P(x), Q(x), with non-negative coefficients. The coefficients of P(x)P(x) is not larger than 20212021 and Q(x)Q(x) has at least one coefficient larger than 20212021. Assume that P(2022)=Q(2022)P(2022) = Q(2022) and P(x),Q(x)P(x), Q(x) has a common rational root pq0\frac{p}{q} \neq 0 for some p,qZp, q \in \mathbb{Z}, (gcd(p,q)=1)(\gcd(p, q) = 1). Prove that
p+nqQ(n)P(n),n=1,2,,2021. |p| + n|q| \leq Q(n) - P(n), \forall n = 1, 2, \dots, 2021.

Solution

Since the coefficients of P(x)P(x) are non-negative, the root x=p/qx = p/q must be negative. Without loss of generality, we assume that p<0,q>0p < 0, q > 0 then p+nq=nqp|p| + n|q| = nq - p. Let R(x)=Q(x)P(x)R(x) = Q(x) - P(x), then R(x)R(x) is an integer polynomial where x=p/qx = p/q is a root. This implies that
R(x)=(qxp)T(x) R(x) = (qx - p)T(x)
where T(x)T(x) is a polynomial with rational coefficients. Since gcd(p,q)=1\text{gcd}(p, q) = 1, by using Gauss lemma for the product of two primitive polynomials, we get T(x)Z[x]T(x) \in \mathbb{Z}[x]. This implies that qnpR(n)qn - p \mid R(n) for all n=1,2,,2021n = 1, 2, \dots, 2021.

Hence, to finish the proof, we just need to show that R(n)>0R(n) > 0 for all n=1,2,,2021n = 1, 2, \dots, 2021. Since x=2022x = 2022 is a root of R(x)R(x), we also can write
R(x)=(x2022)H(x) R(x) = (x - 2022)H(x)
in which H(x)=amxm+am1xm1++a1x+a0H(x) = a_m x^m + a_{m-1} x^{m-1} + \dots + a_1 x + a_0 is an polynomial with integer coefficients. Note that n2022<0n - 2022 < 0 for all n=1,2,,2021n = 1, 2, \dots, 2021, so it suffices to show that H(n)<0H(n) < 0 for all n=1,2,,2021n = 1, 2, \dots, 2021.

By expanding the product in the right hand side, we can find out that the coefficient of xix^i is ai12022aia_{i-1} - 2022a_i for 1im1 \le i \le m and the constant is 2022a0-2022a_0. On the other hand, since the coefficients of P(x)P(x) are not larger than 20212021 then the coefficients of R(x)R(x) are not less than 2021-2021. From this, a00a_0 \le 0. Suppose that there exists some coefficients of H(x)H(x) are positive, denote by >0\ell > 0, the smallest value of such indices. Thus, a>0a_\ell > 0 and a10a_{\ell-1} \le 0 which implies that
a12022a02022=2022. a_{\ell-1} - 2022a_{\ell} \le 0 - 2022 = -2022.
This contradiction show that all coefficients of H(x)H(x) is non-positive. But they can not all zero, otherwise Q(x)P(x)Q(x) \equiv P(x) but Q(x)Q(x) has at least one coefficient larger than 20212021. In conclusion, H(n)<0H(n) < 0 for all n=1,2,,2021n = 1, 2, \dots, 2021. Therefore,
Q(n)P(n)=R(n)qnp=qn+p, Q(n) - P(n) = R(n) \ge qn - p = |q|n + |p|,
for n=1,2,,2021n = 1, 2, \dots, 2021. \square

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.