uniolympiads English

IMC 2011, Ημέρα 2, Θέμα 4

Let f(x)f(x) be a polynomial with real coefficients of degree nn. Suppose that f(k)−f(m)k−m\frac{f(k) - f(m)}{k - m} is an integer for all integers 0≤k<m≤n0 \le k < m \le n. Prove that a−ba - b divides f(a)−f(b)f(a) - f(b) for all pairs of distinct integers aa and bb.

Fedor Petrov, St. Petersburg

Πρωτότυπο από το επίσημο PDFf (k) − f (m) is an integer k − m for all integers 0 ≤ k < m ≤ n. Prove that a − b divides f (a) − f (b) for all pairs of distinct integers a and b. Fedor Petrov, St. Petersburg Problem 4. Let f (x) be a polynomial with real coefficients of degree n. Suppose that

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

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

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

Επίσημη λύση

Fedor Petrov, St. Petersburg

Solution 1. We need the following

Lemma. Denote the least common multiple of 1,2,…,k1,2,\ldots,k by L(k)L(k), and define

hk(x)=L(k)⋅(xk)(k=1,2,…).h_k(x)=L(k)\cdot\binom{x}{k}\qquad(k=1,2,\ldots).
Then the polynomial hk(x)h_k(x) satisfies the condition, i.e. a−ba-b divides hk(a)−hk(b)h_k(a)-h_k(b) for all pairs of distinct integers aa, bb.

Proof. It is known that

(ak)=∑j=0k(a−bj)(bk−j).\binom{a}{k}=\sum_{j=0}^k\binom{a-b}{j}\binom{b}{k-j}.
(This formula can be proved by comparing the coefficient of xkx^k in (1+x)a(1+x)^a and (1+x)a−b(1+x)b(1+x)^{a-b}(1+x)^b.) From here we get
hk(a)−hk(b)=L(K)((ak)−(bk))=L(K)∑j=1k(a−bj)(bk−j)=(a−b)∑j=1kL(k)j(a−b−1j−1)(bk−j).h_k(a)-h_k(b)=L(K)\left(\binom{a}{k}-\binom{b}{k}\right)=L(K)\sum_{j=1}^k\binom{a-b}{j}\binom{b}{k-j}=(a-b)\sum_{j=1}^k\frac{L(k)}{j}\binom{a-b-1}{j-1}\binom{b}{k-j}.
On the right-hand side all fractions L(k)j\frac{L(k)}{j} are integers, so the right-hand side is a multiple of (a,b)(a,b). The lemma is proved.

Expand the polynomial ff in the basis 1,(x1),(x2),…1,\binom{x}{1},\binom{x}{2},\ldots as

f(x)=A0+A1(x1)+A2(x2)+⋯+An(xn).(1)f(x)=A_0+A_1\binom{x}{1}+A_2\binom{x}{2}+\dots+A_n\binom{x}{n}.\tag{1}
We prove by induction on jj that AjA_j is a multiple of L(j)L(j) for 1≤j≤n1\le j\le n. (In particular, AjA_j is an integer for j≥1j\ge1.) Assume that L(j)L(j) divides AjA_j for 1≤j≤m−11\le j\le m-1. Substituting mm and some k∈{0,1,…,m−1}k\in\{0,1,\ldots,m-1\} in (1),
f(m)−f(k)m−k=∑j=1m−1AjL(j)⋅hj(m)−hj(k)m−k+Amm−k.\frac{f(m)-f(k)}{m-k}=\sum_{j=1}^{m-1}\frac{A_j}{L(j)}\cdot\frac{h_j(m)-h_j(k)}{m-k}+\frac{A_m}{m-k}.
Since all other terms are integers, the last term Amm−k\frac{A_m}{m-k} is also an integer. This holds for all 0≤k<m0\le k<m, so AmA_m is an integer that is divisible by L(m)L(m).

Hence, AjA_j is a multiple of L(j)L(j) for every 1≤j≤n1\le j\le n. By the lemma this implies the problem statement.

Solution 2. The statement of the problem follows immediately from the following claim, applied to the polynomial g(x,y)=f(x)−f(y)x−yg(x,y)=\frac{f(x)-f(y)}{x-y}.

Claim. Let g(x,y)g(x,y) be a real polynomial of two variables with total degree less than nn. Suppose that g(k,m)g(k,m) is an integer whenever 0≤k<m≤n0\le k<m\le n are integers. Then g(k,m)g(k,m) is a integer for every pair k,mk,m of integers.

Proof. Apply induction on nn. If n=1n=1 then gg is a constant. This constant can be read from g(0,1)g(0,1) which is an integer, so the claim is true.

Now suppose that n≥2n\ge2 and the claim holds for n−1n-1. Consider the polynomials

g1(x,y)=g(x+1,y+1)−g(x,y+1)andg2(x,y)=g(x,y+1)−g(x,y).(1)g_1(x,y)=g(x+1,y+1)-g(x,y+1)\quad\text{and}\quad g_2(x,y)=g(x,y+1)-g(x,y).\tag{1}
For every pair 0≤k<m≤n−10\le k<m\le n-1 of integers, the numbers g(k,m)g(k,m), g(k,m+1)g(k,m+1) and g(k+1,m+1)g(k+1,m+1) are all integers, so g1(k,m)g_1(k,m) and g2(k,m)g_2(k,m) are integers, too. Moreover, in (1) the maximal degree terms of gg cancel out, so deg⁡g1,deg⁡g2<deg⁡g\deg g_1,\deg g_2<\deg g. Hence, we can apply the induction hypothesis to the polynomials g1g_1 and g2g_2 and we thus have g1(k,m),g2(k,m)∈Zg_1(k,m),g_2(k,m)\in\mathbb Z for all k,m∈Zk,m\in\mathbb Z.

In view of (1), for all k,m∈Zk,m\in\mathbb Z, we have that

(a) g(0,1)∈Zg(0,1)\in\mathbb Z;

(b) g(k,m)∈Zg(k,m)\in\mathbb Z if and only if g(k+1,m+1)∈Zg(k+1,m+1)\in\mathbb Z;

(c) g(k,m)∈Zg(k,m)\in\mathbb Z if and only if g(k,m+1)∈Zg(k,m+1)\in\mathbb Z.

For arbitrary integers k,mk,m, apply (b) ∣k∣|k| times then apply (c) ∣m−k−1∣|m-k-1| times as

g(k,m)∈Z⇔…⇔g(0,m−k)∈Z⇔…⇔g(0,1)∈Z.g(k,m)\in\mathbb Z\Leftrightarrow\ldots\Leftrightarrow g(0,m-k)\in\mathbb Z\Leftrightarrow\ldots\Leftrightarrow g(0,1)\in\mathbb Z.
Hence, g(k,m)∈Zg(k,m)\in\mathbb Z. The claim has been proved.

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

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

Πώς πήγε;