5
$\begingroup$

I'm dealing with the test of the International Mathematics Competition for University Students, 2011, and I've had a lot of difficulties, so I hope someone could help me to discuss the questions.

I've posted before the questions 2, 3 and 5, these last still open.

The question 4 says:

Let be $f(x)$ a polynomial with real coeficients and degree $n$. Supose that $\dfrac{f(k)-f(m)}{k-m}$ is integer for all the integers $0\leq k\lt m\leq n$. Prove that $a-b$ divides $f(a)-f(b)$ for any couple of distinct integers $a$ and $b$.

The only substantial thing that I've got is that:

Given any $k\in\{1,2,3,\dots,n-1\}$, we have

$\dfrac{f(k)-f(0)}{k}\in\mathbb{Z}$.

So,

$f(k)-f(0)$ is integer by any $k\in\{1,2,3,\dots,n-1\}$.

I also have thinked that derivatives can be some relation, because of the type of fraction...

I thank very much.

Important Edit (October, 04)

I've found a document with these solutions and I'm studying them. These are the documents: http://www.imc-math.org.uk/imc2011/imc2011-day2-solutions.pdf and http://www.imc-math.org.uk/imc2011/imc2011-day1-solutions.pdf.

$\endgroup$
  • 3
    $\begingroup$ Seems like maybe $f(x)$ must have only integer coefficients (except possibly for the constant). $\endgroup$ – Alex R. Oct 4 '18 at 21:25
1
$\begingroup$

I don't think the derivative comes anywhere into this. However, the discrete version, i.e., forward differences, does come in in a sense. I'll just sketch a proof.

Let $g(x)=\frac{f(x)-f(0)}{x}$. Then $g(1),g(2),\dots,g(n-1)\in\mathbb{Z}$. Moreover, since $g$ is a polynomial of degree $n-1$, we have $$ 0=\Delta^n[g](x)=\sum_{k=0}^n\binom{n}{k}(-1)^{n-k}g(x+k) $$ giving $g(\mathbb{Z})\subseteq\mathbb{Z}$ inductively. Thus $$ g(x)=\sum_{k=0}^{n-1} c_k\binom{x}{k} $$ with $c_k\in\mathbb{Z}$, i.e., $$ f(x)=f(0)+x\sum_{k=0}^{n-1} c_k\binom{x}{k}=f(0)+\sum_{k=1}^n c'_k\binom{x}{k}. $$ with $c'_k\in\mathbb{Z}$.

Moreover, by examining deeper into the conditon $\dfrac{f(k)-f(m)}{k-m}\in\mathbb{Z}$ for $0\leq k<m\leq n$ and induction on $k$ noting $$ \begin{align*} \binom{a}{k}-\binom{b}{k}&=\sum_{j=1}^k\binom{a-b}{j}\binom{b}{k-j}\\ &=(a-b)\sum_{j=1}^k\frac1j\binom{a-b-1}{j-1}\binom{b}{k-j} \end{align*} $$ one can prove $c'_k$ is an integer multiple of $L_k:=\operatorname{lcm}(1,2,\dots,k)$ for each $k$. Hence the result follows.

$\endgroup$
  • $\begingroup$ Thanks very much, I'm trying to study your proof. I think I need study more about polynomials, but I believe that your proof is correct, so I'll accept your answer and continue studying. Thanks a lot for the great help! $\endgroup$ – Na'omi Oct 5 '18 at 15:19
  • 1
    $\begingroup$ Recall one way to define the binoimial coefficient $\binom{n}{k}$ is as the number of $k$-subsets of an $n$-set. The identity is easy obtained by splitting $[a]$ into a $b$-subset and a $a-b$-subset and consider how to choose a $k$-subset. The $\Delta$ is the forward difference operator $\Delta[f](n):=f(n+1)-f(n)$. $\endgroup$ – user10354138 Oct 12 '18 at 21:14
  • $\begingroup$ I thank you very much. For the first doubt, moreover, I've open a post here: math.stackexchange.com/questions/2953142/binomials-extensions. And for the second doubt, I didn't know about this difference operator, I'm researching abou this. Thanks very much and sorry my difficulties. $\endgroup$ – Na'omi Oct 12 '18 at 21:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.