IMC 2011 · Day 2 · P9

We need the following

Lemma. Denote the least common multiple of $1, 2, \dots, k$ by $L(k)$, and define $$h_k(x) = L(k) \cdot \binom{x}{k} \quad (k = 1, 2, \dots).$$ Then the polynomial $h_k(x)$ satisfies the condition, i.e.\ $a - b$ divides $h_k(a) - h_k(b)$ for all pairs of distinct integers $a$, $b$.

Proof. It is known that $$\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 $x^k$ in $(1+x)^a$ and $(1+x)^{a-b} (1+x)^b$.) From here we get $$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 $\frac{L(k)}{j}$ 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, \binom{x}{1}, \binom{x}{2}, \dots$ as $$\tag{1} f(x) = A_0 + A_1 \binom{x}{1} + A_2 \binom{x}{2} + \dots + A_n \binom{x}{n}.$$ We prove by induction on $j$ that $A_j$ is a multiple of $L(j)$ for $1 \le j \le n$. (In particular, $A_j$ is an integer for $j \ge 1$.) Assume that $L(j)$ divides $A_j$ for $1 \le j \le m-1$. Substituting $m$ and some $k \in \{0, 1, \dots, m-1\}$ in (1), $$\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 $\frac{A_m}{m-k}$ is also an integer. This holds for all $0 \le k < m$, so $A_m$ is an integer that is divisible by $L(m)$.

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

The statement of the problem follows immediately from the following claim, applied to the polynomial $g(x, y) = \dfrac{f(x) - f(y)}{x - 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 \le k < m \le 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 \ge 2$ and the claim holds for $n - 1$. Consider the polynomials $$\tag{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).$$ For every pair $0 \le k < m \le n-1$ of integers, the numbers $g(k, m)$, $g(k, m+1)$ and $g(k+1, m+1)$ are all integers, so $g_1(k, m)$ and $g_2(k, m)$ are integers, too. Moreover, in (1) the maximal degree terms of $g$ cancel out, so $\deg g_1, \deg g_2 < \deg g$. Hence, we can apply the induction hypothesis to the polynomials $g_1$ and $g_2$ and we thus have $g_1(k, m), g_2(k, m) \in \mathbb{Z}$ for all $k, m \in \mathbb{Z}$.

In view of (1), for all $k, m \in \mathbb{Z}$, we have that

(a) $g(0, 1) \in \mathbb{Z}$;

(b) $g(k, m) \in \mathbb{Z}$ if and only if $g(k+1, m+1) \in \mathbb{Z}$;

(c) $g(k, m) \in \mathbb{Z}$ if and only if $g(k, m+1) \in \mathbb{Z}$.

For arbitrary integers $k, m$, apply (b) $|k|$ times then apply (c) $|m - k - 1|$ times as $$g(k, m) \in \mathbb{Z} \Leftrightarrow \dots \Leftrightarrow g(0, m-k) \in \mathbb{Z} \Leftrightarrow \dots \Leftrightarrow g(0, 1) \in \mathbb{Z}.$$ Hence, $g(k, m) \in \mathbb{Z}$. The claim has been proved.