uniolympiads Ελληνικά

IMC 2011, Day 2, Problem 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

Original from the official 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

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

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.

Transcribed from the official solutions, pages 3–4. 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?