uniolympiads English

IMC 2006, Ημέρα 1, Θέμα 4

Let ff be a rational function (i.e. the quotient of two real polynomials) and suppose that f(n)f(n) is an integer for infinitely many integers nn. Prove that ff is a polynomial.

Πρωτότυπο από το επίσημο PDFLet f be a rational function (i.e. the quotient of two real polynomials) and suppose that f (n) is an integer for infinitely many integers n. Prove that f is a polynomial. (20 points)

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

Solution. Let SS be an infinite set of integers such that rational function f(x)f(x) is integral for all x∈Sx\in S.

Suppose that f(x)=p(x)/q(x)f(x)=p(x)/q(x) where pp is a polynomial of degree kk and qq is a polynomial of degree nn. Then p,qp,q are solutions to the simultaneous equations p(x)=q(x)f(x)p(x)=q(x)f(x) for all x∈Sx\in S that are not roots of qq. These are linear simultaneous equations in the coefficients of p,qp,q with rational coefficients. Since they have a solution, they have a rational solution.

Thus there are polynomials p′,q′p',q' with rational coefficients such that p′(x)=q′(x)f(x)p'(x)=q'(x)f(x) for all x∈Sx\in S that are not roots of qq. Multiplying this with the previous equation, we see that p′(x)q(x)f(x)=p(x)q′(x)f(x)p'(x)q(x)f(x)=p(x)q'(x)f(x) for all x∈Sx\in S that are not roots of qq. If xx is not a root of pp or qq, then f(x)≠0f(x)\ne0, and hence p′(x)q(x)=p(x)q′(x)p'(x)q(x)=p(x)q'(x) for all x∈Sx\in S except for finitely many roots of pp and qq. Thus the two polynomials p′qp'q and pq′pq' are equal for infinitely many choices of value. Thus p′(x)q(x)=p(x)q′(x)p'(x)q(x)=p(x)q'(x). Dividing by q(x)q′(x)q(x)q'(x), we see that p′(x)/q′(x)=p(x)/q(x)=f(x)p'(x)/q'(x)=p(x)/q(x)=f(x). Thus f(x)f(x) can be written as the quotient of two polynomials with rational coefficients. Multiplying up by some integer, it can be written as the quotient of two polynomials with integer coefficients.

Suppose f(x)=p′′(x)/q′′(x)f(x)=p''(x)/q''(x) where p′′p'' and q′′q'' both have integer coefficients. Then by Euler's division algorithm for polynomials, there exist polynomials ss and rr, both of which have rational coefficients such that p′′(x)=q′′(x)s(x)+r(x)p''(x)=q''(x)s(x)+r(x) and the degree of rr is less than the degree of q′′q''. Dividing by q′′(x)q''(x), we get that f(x)=s(x)+r(x)/q′′(x)f(x)=s(x)+r(x)/q''(x). Now there exists an integer NN such that Ns(x)Ns(x) has integral coefficients. Then Nf(x)−Ns(x)Nf(x)-Ns(x) is an integer for all x∈Sx\in S. However, this is equal to the rational function Nr/q′′Nr/q'', which has a higher degree denominator than numerator, so tends to 0 as xx tends to ∞\infty. Thus for all sufficiently large x∈Sx\in S, Nf(x)−Ns(x)=0Nf(x)-Ns(x)=0 and hence r(x)=0r(x)=0. Thus rr has infinitely many roots, and is 0. Thus f(x)=s(x)f(x)=s(x), so ff is a polynomial.

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδα 2. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;