uniolympiads Ελληνικά

IMC 2008, Day 2, Problem 4

Let Z[x]\mathbb{Z}[x] be the ring of polynomials with integer coefficients, and let f(x),g(x)∈Z[x]f(x), g(x) \in \mathbb{Z}[x] be nonconstant polynomials such that g(x)g(x) divides f(x)f(x) in Z[x]\mathbb{Z}[x]. Prove that if the polynomial f(x)−2008f(x) - 2008 has at least 8181 distinct integer roots, then the degree of g(x)g(x) is greater than 55.

Original from the official PDFLet Z[x] be the ring of polynomials with integer coefficients, and let f (x), g(x) ∈ Z[x] be nonconstant polynomials such that g(x) divides f (x) in Z[x]. Prove that if the polynomial f (x)−2008 has at least 81 distinct integer roots, then the degree of g(x) is greater than 5.

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

Solution. Let f(x)=g(x)h(x)f(x) = g(x)h(x) where h(x)h(x) is a polynomial with integer coefficients.

Let a1,…,a81a_1, \ldots, a_{81} be distinct integer roots of the polynomial f(x)−2008f(x) - 2008. Then f(ai)=g(ai)h(ai)=2008f(a_i) = g(a_i)h(a_i) = 2008 for i=1,…,81i = 1, \ldots, 81, Hence, g(a1),…,g(a81)g(a_1), \ldots, g(a_{81}) are integer divisors of 2008.

Since 2008=23⋅2512008 = 2^3\cdot 251 (2,251(2, 251 are primes) then 2008 has exactly 16 distinct integer divisors (including the negative divisors as well). By the pigeonhole principle, there are at least 6 equal numbers among g(a1),…,g(a81)g(a_1), \ldots, g(a_{81}) (because 81>16⋅581 > 16\cdot 5). For example, g(a1)=g(a2)=…=g(a6)=cg(a_1) = g(a_2) = \ldots = g(a_6) = c. So g(x)−cg(x) - c is a nonconstant polynomial which has at least 6 distinct roots (namely a1,…,a6a_1, \ldots, a_6). Then the degree of the polynomial g(x)−cg(x) - c is at least 6.

Transcribed from the official solutions, page 1. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?