uniolympiads English

IMC 2008, Ημέρα 1, Θέμα 3

Let pp be a polynomial with integer coefficients and let a1<a2<⋯<aka_1 < a_2 < \dots < a_k be integers.

a) Prove that there exists a∈Za \in \mathbb{Z} such that p(ai)p(a_i) divides p(a)p(a) for all i=1,2,…,ki = 1, 2, \dots, k.

b) Does there exist an a∈Za \in \mathbb{Z} such that the product p(a1)⋅p(a2)⋅…⋅p(ak)p(a_1) \cdot p(a_2) \cdot \ldots \cdot p(a_k) divides p(a)p(a)?

Πρωτότυπο από το επίσημο PDFLet p be a polynomial with integer coefficients and let a 1 < a 2 < . . . < a k be integers. a) Prove that there exists a ∈ Z such that p(a i ) divides p(a) for all i = 1, 2, . . . , k. b) Does there exist an a ∈ Z such that the product p(a 1 ) · p(a 2 ) · . . . · p(a k ) divides p(a)?

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

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

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

Επίσημη λύση

Solution. The theorem is obvious if p(ai)=0p(a_i) = 0 for some ii, so assume that all p(ai)p(a_i) are nonzero and pairwise different.

There exist numbers ss, tt such that s∣p(a1)s|p(a_1), t∣p(a2)t|p(a_2), st=lcm⁡(p(a1),p(a2))st = \operatorname{lcm}(p(a_1), p(a_2)) and gcd⁡(s,t)=1\gcd(s,t) = 1.

As ss, tt are relatively prime numbers, there exist m,n∈Zm, n \in \mathbb{Z} such that a1+sn=a2+tm=:b2a_1 + sn = a_2 + tm =: b_2. Obviously s∣p(a1+sn)−p(a1)s|p(a_1+sn) - p(a_1) and t∣p(a2+tm)−p(a2)t|p(a_2+tm) - p(a_2), so st∣p(b2)st|p(b_2).

Similarly one obtains b3b_3 such that p(a3)∣p(b3)p(a_3)|p(b_3) and p(b2)∣p(b3)p(b_2)|p(b_3) thus also p(a1)∣p(b3)p(a_1)|p(b_3) and p(a2)∣p(b3)p(a_2)|p(b_3).

Reasoning inductively we obtain the existence of a=bka = b_k as required.

The polynomial p(x)=2x2+2p(x) = 2x^2 + 2 shows that the second part of the problem is not true, as p(0)=2p(0) = 2, p(1)=4p(1) = 4 but no value of p(a)p(a) is divisible by 88 for integer aa.

Remark. One can assume that the p(ai)p(a_i) are nonzero and ask for aa such that p(a)p(a) is a nonzero multiple of all p(ai)p(a_i). In the solution above, it can happen that p(a)=0p(a) = 0. But every number p(a+np(a1)p(a2)…p(ak))p(a + np(a_1)p(a_2)\ldots p(a_k)) is also divisible by every p(ai)p(a_i), since the polynomial is nonzero, there exists nn such that p(a+np(a1)p(a2)…p(ak))p(a + np(a_1)p(a_2)\ldots p(a_k)) satisfies the modified thesis.

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

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

Πώς πήγε;