Home > Olympiad > IMC 2011 Day 2 Problem 4

## IMC 2011 Day 2 Problem 4

Let $f$ be a polynomial with real coefficients of degree $n$. Suppose that $\displaystyle \frac{f(x)-f(y)}{x-y}$ is an integer for all $0 \leq x. Prove that $a-b | f(a)-f(b)$ for all distinct integers $a,b$.

1. August 1, 2011 at 5:34 pm

Let $f(p) = a_np^n + a^{n-1}p^{n-1}+........+a_0$ be a polynomial in $p$ of degree $n$, where each $a_i$ belongs to $\Bbb{R}$. It is given that $\frac{f(x)-f(y)}{x-y}$ is an integer for $0 \leq x, So $\frac{f(x)-f(y)}{x-y}=k$ (say) _ _ _ _ (1), this yields that $f(y) = ky + a_0$. (By substituting $x = 0$ in equation (1) and equating the corresponding co-efficient) _ _ _ _ (2) and note that y lies between $0$ and $n$. Equation (1) conveys, whenever $x$ lies between $0$ and $n$, the curve $f(x)$ reduces to a straight line.
Now consider the expression $\frac{f(a)-f(b)}{a-b}$, let’s assume that ‘$a$’ be any integer but $b$ be an integer such that $b$ lies between $0$ and $n$. ( even though it is a special case, first we will prove the problem for this case, which in turn leads to the solution when both a and b are any integers.)
We will take induction on $a$, whenever $a = 0$ the result is trivially true. Suppose $\frac{f(a)-f(b)}{a-b}$ be an integer ‘$m$’ for all integers less than or equal to $a$, using equation (2) and expanding $f(a)$, equating the corresponding co-efficient we will get $f(a) = ka + a_0$ _ _ _ (3)( note that it is true for all integer less than or equal to $a$). Equation (3) says that a polynomial of degree $n$ can be written as a polynomial of degree $1$ for all integers less than or equal to a for any positive integer $n$. Now consider $f(a+1) = a_n(a+1)^n + .....+ a_0$, on expanding and using equation (3) we will get $f(a+1) = k(a+1) + a_0$, therefore $\frac{f(a+1)-f(b)}{(a+1)-b}$ is an integer. This closes the induction and proves that $a-b$ divides $f(a)-f(b)$ for any integer a and an integer $b$ lies between $0$ and $n$.
Finally consider any distinct integers $a$ and $c$, $f(a)-f(c)$ can be written as $(f(a)-f(b))-(f(c)- f(b))$, where $b$ lies between $0$ and $n$, therefore $f(a)- f(b) = K(a - b)$ and $f(c) - f(b) = K(c - b)$, from the last paragraph. Therefore $a - c$ divides $f(a) - f(c)$.
Hence the proof.

• August 1, 2011 at 9:11 pm

I don’t think your proof is correct. The problem says that the ratio $f(x)-f(y)/(x-y)$ is AN integer for every $x,y$ between $0$ and $n$, not THE same integer. This means that for every $x,y$ there can be a different $k$.

• August 1, 2011 at 9:11 pm

I don’t think your proof is correct. The problem says that the ratio $f(x)-f(y)/(x-y)$ is AN integer for every $x,y$ between $0$ and $n$, not THE same integer. This means that for every $x,y$ there can be a different $k$.

• August 2, 2011 at 5:17 am

Yea, i know that but whether its same integer or different, the idea is that curve is reduced to a straight line in that range and that is the main point in the proof.

( Readers, here i am not able to type powers and subscripts so i assume that you will make out)

Let f(p) = anpn + an-1pn-1+……..+a0 be a polynomial in p of degree n, where each ai belongs to R. It is given that f(x) – f(y) / x-y is an integer for 0≤x<y≤n, So { f(x) – f(y) / x-y} = k ( say) _ _ _ _ (1), this yields that f(y) = ky + a0. (By substituting x = 0 in equation (1) and equating the corresponding co-efficient) _ _ _ _ (2) and note that y lies between 0 and n. Equation (1) conveys, whenever x lies between 0 and n, the curve f(x) reduces to a straight line.
Now consider the expression {f(a) – f(b)} / a-b, let’s assume that ‘a’ be any integer but b be an integer such that b lies between 0 and n. ( even though it is a special case, first we will prove the problem for this case, which in turn leads to the solution when both a and b are any integers.)
We will take induction on a, whenever a = 0 the result is trivially true. Suppose {f(a) – f(b)} / a-b be an integer ‘m’ for all integers less than or equal to a, using equation (2) and expanding f(a), equating the corresponding co-efficient we will get f(a) = ka + a0 _ _ _ (3)( note that it is true for all integer less than or equal to a). Equation (3) says that a polynomial of degree n can be written as a polynomial of degree 1 for all integers less than or equal to a for any positive integer n. Now consider f(a+1) = an(a+1)n + …..+ a0, on expanding and using equation (3) we will get f(a+1) = k(a+1) + a0, therefore {f(a+1) – f(b)}/ (a+1) – b is an integer. This closes the induction and proves that (a – b) divides f(a) – f(b) for any integer a and an integer b lies between 0 and n.
Finally consider any distinct integers a and c, f(a) – f(c) can be written as {f(a) – f(b)} – { f(c) – f(b)}, where b lies between 0 and n, therefore f(a) – f(b) = K(a – b) and f(c) – f(b) = K(c – b), { from the last paragraph}. Therefore a – c divides f(a) – f(c).
Hence the proof.

• August 2, 2011 at 5:20 am

Even if you write different integer the proof remains the same.

Yea, i know that but whether its same integer or different, the idea is that curve is reduced to a straight line in that range and that is the main point in the proof.

( Readers, here i am not able to type powers and subscripts so i assume that you will make out)

Let f(p) = anpn + an-1pn-1+……..+a0 be a polynomial in p of degree n, where each ai belongs to R. It is given that f(x) – f(y) / x-y is an integer for 0≤x<y≤n, So { f(x) – f(y) / x-y} = k ( say) _ _ _ _ (1), this yields that f(y) = ky + a0. (By substituting x = 0 in equation (1) and equating the corresponding co-efficient) _ _ _ _ (2) and note that y lies between 0 and n. Equation (1) conveys, whenever x lies between 0 and n, the curve f(x) reduces to a straight line.
Now consider the expression {f(a) – f(b)} / a-b, let’s assume that ‘a’ be any integer but b be an integer such that b lies between 0 and n. ( even though it is a special case, first we will prove the problem for this case, which in turn leads to the solution when both a and b are any integers.)
We will take induction on a, whenever a = 0 the result is trivially true. Suppose {f(a) – f(b)} / a-b be an integer ‘m’ for all integers less than or equal to a, using equation (2) and expanding f(a), equating the corresponding co-efficient we will get f(a) = ka + a0 _ _ _ (3)( note that it is true for all integer less than or equal to a). Equation (3) says that a polynomial of degree n can be written as a polynomial of degree 1 for all integers less than or equal to a for any positive integer n. Now consider f(a+1) = an(a+1)n + …..+ a0, on expanding and using equation (3) we will get f(a+1) = k(a+1) + a0, therefore {f(a+1) – f(b)}/ (a+1) – b is an integer. This closes the induction and proves that (a – b) divides f(a) – f(b) for any integer a and an integer b lies between 0 and n.
Finally consider any distinct integers a and c, f(a) – f(c) can be written as {f(a) – f(b)} – { f(c) – f(b)}, where b lies between 0 and n, therefore f(a) – f(b) = K(a – b) and f(c) – f(b) = K(c – b), { from the last paragraph}. Therefore a – c divides f(a) – f(c).
Hence the proof.

2. August 2, 2011 at 5:54 am

Even if you write different integer the proof remains the same.

Yea, i know that but whether its same integer or different, the idea is that curve is reduced to a straight line in that range and that is the main point in the proof.

( Readers, here i am not able to type powers and subscripts so i assume that you will make out)

Let f(p) = anpn + an-1pn-1+……..+a0 be a polynomial in p of degree n, where each ai belongs to R. It is given that f(x) – f(y) / x-y is an integer for 0≤x<y≤n, So { f(x) – f(y) / x-y} = k ( say) _ _ _ _ (1), this yields that f(y) = my + a0. (By substituting x = 0 in equation (1) and equating the corresponding co-efficient) _ _ _ _ (2) and note that y lies between 0 and n. Equation (1) conveys, whenever x lies between 0 and n, the curve f(x) reduces to a straight line.
Now consider the expression {f(a) – f(b)} / a-b, let’s assume that ‘a’ be any integer but b be an integer such that b lies between 0 and n. ( even though it is a special case, first we will prove the problem for this case, which in turn leads to the solution when both a and b are any integers.), let f(b) = qb + a0.
We will take induction on a, whenever a = 0 the result is trivially true. Suppose {f(a) – f(b)} / a-b be an integer ‘r’ for all integers less than or equal to a, using equation (2) and expanding f(a), equating the corresponding co-efficient we will get f(a) = qa + a0 _ _ _ (3),HERE THE HIGHLIGHT IS CO-EFFICIENT OF a IN f(a) IS SAME AS THAT OF b IN f(b). (note that it is true for all integer less than or equal to a). Equation (3) says that a polynomial of degree n can be written as a polynomial of degree 1 for all integers less than or equal to a for any positive integer n. Now consider f(a+1) = an(a+1)n + …..+ a0, on expanding and using equation (3) we will get f(a+1) = q(a+1) + a0, therefore {f(a+1) – f(b)}/ (a+1) – b is an integer. This closes the induction and proves that (a – b) divides f(a) – f(b) for any integer a and an integer b lies between 0 and n.
Finally consider any distinct integers a and c, f(a) – f(c) can be written as {f(a) – f(b)} – { f(c) – f(b)}, where b lies between 0 and n, therefore f(a) – f(b) = K(a – b) and f(c) – f(b) = K(c – b), { from the last paragraph}. Therefore a – c divides f(a) – f(c).
Hence the proof.

Dear Beni,

I have highlighted a point in the proof, it is written in Caps lock.

• August 2, 2011 at 9:49 am

It is not correct. Please try to bring strong arguments to your conclusions. What you say is that the polynomials are of degree $1$, and this is again not true.

3. August 2, 2011 at 3:55 pm

could you give me your solution?