Fedor Petrov, St. Petersburg
Solution 1. We need the following
Lemma. Denote the least common multiple of 1,2,…,k by L(k), and define
hk(x)=L(k)⋅(kx)(k=1,2,…).
Then the polynomial
hk(x) satisfies the condition, i.e.
a−b divides
hk(a)−hk(b) for all pairs of distinct integers
a,
b.
Proof. It is known that
(ka)=j=0∑k(ja−b)(k−jb).
(This formula can be proved by comparing the coefficient of
xk in
(1+x)a and
(1+x)a−b(1+x)b.) From here we get
hk(a)−hk(b)=L(K)((ka)−(kb))=L(K)j=1∑k(ja−b)(k−jb)=(a−b)j=1∑kjL(k)(j−1a−b−1)(k−jb).
On the right-hand side all fractions
jL(k) are integers, so the right-hand side is a multiple of
(a,b). The lemma is proved.
Expand the polynomial f in the basis 1,(1x),(2x),… as
f(x)=A0+A1(1x)+A2(2x)+⋯+An(nx).(1)
We prove by induction on
j that
Aj is a multiple of
L(j) for
1≤j≤n. (In particular,
Aj is an integer for
j≥1.) Assume that
L(j) divides
Aj for
1≤j≤m−1. Substituting
m and some
k∈{0,1,…,m−1} in (1),
m−kf(m)−f(k)=j=1∑m−1L(j)Aj⋅m−khj(m)−hj(k)+m−kAm.
Since all other terms are integers, the last term
m−kAm is also an integer. This holds for all
0≤k<m, so
Am is an integer that is divisible by
L(m).
Hence, Aj is a multiple of L(j) for every 1≤j≤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)=x−yf(x)−f(y).
Claim. Let g(x,y) be a real polynomial of two variables with total degree less than n. Suppose that g(k,m) is an integer whenever 0≤k<m≤n are integers. Then g(k,m) is a integer for every pair k,m of integers.
Proof. Apply induction on n. If n=1 then g is a constant. This constant can be read from g(0,1) which is an integer, so the claim is true.
Now suppose that n≥2 and the claim holds for n−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)
For every pair
0≤k<m≤n−1 of integers, the numbers
g(k,m),
g(k,m+1) and
g(k+1,m+1) are all integers, so
g1(k,m) and
g2(k,m) are integers, too. Moreover, in (1) the maximal degree terms of
g cancel out, so
degg1,degg2<degg. Hence, we can apply the induction hypothesis to the polynomials
g1 and
g2 and we thus have
g1(k,m),g2(k,m)∈Z for all
k,m∈Z.
In view of (1), for all k,m∈Z, we have that
(a) g(0,1)∈Z;
(b) g(k,m)∈Z if and only if g(k+1,m+1)∈Z;
(c) g(k,m)∈Z if and only if g(k,m+1)∈Z.
For arbitrary integers k,m, apply (b) ∣k∣ times then apply (c) ∣m−k−1∣ times as
g(k,m)∈Z⇔…⇔g(0,m−k)∈Z⇔…⇔g(0,1)∈Z.
Hence,
g(k,m)∈Z. The claim has been proved.
Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 3–4. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.