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<y \leq n. Prove that a-b | f(a)-f(b) for all distinct integers a,b.

Advertisements
Categories: Olympiad Tags:
  1. Vijay Joshi
    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<y \leq n, 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.

      • Vijay Joshi
        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.

      • Vijay Joshi
        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. Vijay Joshi
    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. Vijay Joshi
    August 2, 2011 at 3:55 pm

    could you give me your solution?

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: