Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. Standard member royalchicken
    CHAOS GHOST!!!
    28 Jan '06 00:30
    Let P be a polynomial of degree 2000 with P(n) = n/(n+1) for n between 0 and 2000 inclusive. What is P(2001)?
  2. Standard member TheMaster37
    Kupikupopo!
    29 Jan '06 21:46
    Originally posted by royalchicken
    Let P be a polynomial of degree 2000 with P(n) = n/(n+1) for n between 0 and 2000 inclusive. What is P(2001)?
    Let's see...I don't notice the trick, but Lagrange polynomials should work.

    P is completely define by the 2001 points given, wich means P(2001) is a fixed value.

    To determine that value you need patience, a computer, or the trick.

    Since I have none of the three mentioned above, I'll leave this to you to demonstrate :p
  3. Standard member royalchicken
    CHAOS GHOST!!!
    29 Jan '06 23:43
    Originally posted by TheMaster37
    Let's see...I don't notice the trick, but Lagrange polynomials should work.

    P is completely define by the 2001 points given, wich means P(2001) is a fixed value.

    To determine that value you need patience, a computer, or the trick.

    Since I have none of the three mentioned above, I'll leave this to you to demonstrate :p
    Actually, someone asked me this, and I did not spot the trick, so I wrote a little program to do it (really just to invert a matrix). I was hoping RHP could think of something cleverer.
  4. 30 Jan '06 11:33
    Originally posted by royalchicken
    Let P be a polynomial of degree 2000 with P(n) = n/(n+1) for n between 0 and 2000 inclusive. What is P(2001)?
    I don't see the trick so I solve it anyway...

    If P(n) = n/(n+1)
    then P(2001) = 2001/2002 = 0,9 995004 995004 995004 ... right?

    Is the trick to realize that n/(n+1) isn't a polynomial so you have to find a Taylor-approximation or someting? But the answer should be same, perhaps only with a residual included.
  5. 30 Jan '06 14:19
    Originally posted by FabianFnas
    I don't see the trick so I solve it anyway...

    If P(n) = n/(n+1)
    then P(2001) = 2001/2002 = 0,9 995004 995004 995004 ... right?

    But he said that P(n)=n/(n+1) for n between 0 and 2000 so I assume that rule is not valid for P(2001), and there is another polynomial that gives n/n+1 for these n and maybe deviates at n=2001. Otherwise, this would be pretty simple, even I can divide two numbers.

    Again. it's just what I assume.
  6. Standard member TheMaster37
    Kupikupopo!
    30 Jan '06 23:11
    Originally posted by fetofs
    But he said that P(n)=n/(n+1) for n between 0 and 2000 so I assume that rule is not valid for P(2001), and there is another polynomial that gives n/n+1 for these n and maybe deviates at n=2001. Otherwise, this would be pretty simple, even I can divide two numbers.

    Again. it's just what I assume.
    Well, a 2000 degree polynomial is completely defined by 2001 points.

    (as a line is defined by two points).

    F(x) = x/(x+1) is not a polynomial, that's easily proven.

    With that P(2001) will most likely NOT be equal to 2000/2001, as the graph of P will increase or decrease rapidly after 2000.
  7. Subscriber AThousandYoung
    It's about respect
    01 Feb '06 01:01
    Originally posted by TheMaster37
    Well, a 2000 degree polynomial is completely defined by 2001 points.

    (as a line is defined by two points).

    F(x) = x/(x+1) is not a polynomial, that's easily proven.

    With that P(2001) will most likely NOT be equal to 2000/2001, as the graph of P will increase or decrease rapidly after 2000.
    We have an infinite number of points here, correct? Or is there an unstated "integers only" rule about what n can be?

    The graph is going to be the graph of y = x/(x+1) until maybe after x=2000. Can one have a polynomial of finite degree be so perfectly smooth? Are we assuming that P(n) = n/(n+1) exactly or is there some rounding assumed?
  8. Standard member royalchicken
    CHAOS GHOST!!!
    02 Feb '06 11:35
    Originally posted by AThousandYoung
    We have an infinite number of points here, correct? Or is there an unstated "integers only" rule about what n can be?

    The graph is going to be the graph of y = x/(x+1) until maybe after x=2000. Can one have a polynomial of finite degree be so perfectly smooth? Are we assuming that P(n) = n/(n+1) exactly or is there some rounding assumed?
    To clarify: P is a polynomial that takes the values stated at integers between 0 and 2000 inclusive, and may take other values at non-integral points.

    There is no rounding.
  9. Standard member psychopath42
    Green Slime
    03 Feb '06 17:43 / 2 edits
    Originally posted by royalchicken
    Let P be a polynomial of degree 2000 with P(n) = n/(n+1) for n between 0 and 2000 inclusive. What is P(2001)?
    Let f(x) = a_1*x + a_2*x(x-1) + a_3*x(x-1)(x-2) + ... + a_2000*x(x-1)(x-2)...(x-1999)
    where
    a_k = (-1)^(k+1)/(k+1)!

    Lemma: f(x) = P(x)

    Proof of lemma:
    It suffices to show that f(n) = n/(n+1) for all integers n=0,...,2000 inclusive.
    For n=0:
    f(0) = 0 is obvious

    For n=1,...,2000:
    f(n) = a_1*n + a_2*n(n-1) + a_3*n(n-1)(n-2) + ... + a_n*n(n-1)(n-2)...(2)(1)
    = n/2! - n(n-1)/3! + n(n-1)(n-2)/4! - ... +/- n(n-1)(n-2)...(2)(1)/(n+1)!
    = 1/(n+1) * [ (n+1)n/2! - (n+1)n(n-1)/3! + (n+1)n(n-1)(n-2)/4! - ... +/- (n+1)n(n-1)(n-2)...(2)(1)/(n+1)! ]
    = 1/(n+1) * [ C(n+1,2) - C(n+1,3) + C(n+1,4) - ... +/- C(n+1,n+1) ]
    = 1/(n+1) * [ - C(n+1,0) + C(n+1,1) ]
    = 1/(n+1) * [ -1 + n + 1 ]
    = n/(n+1)

    Note that the combinatorial formula
    sum( (-1)^k*C(n+1,k) )_{k=0}^{n+1} = 0
    was used.

    Corollary: f(2001) = 1000/1001

    f(2001) = a_1*2001 + a_2*(2001)(2000) + a_3*(2001)(2000)(1999) + ... + a_2000*(2001)(2000)(1999)...(3)(2)
    = 2001/2! - (2001)(2000)/3! + (2001)(2000)(1999)/4! - ... - (2001)(2000)(1999)...(3)(2)/2001!
    = 1/2002 * [ (2002)(2001)/2! - (2002)(2001)(2000)/3! + (2002)(2001)(2000)(1999)/4! - ... - (2002)(2001)(2000)(1999)...(2)/2001! ]
    = 1/2002 * [ C(2002,2) - C(2002,3) + C(2002,4) - ... - C(2002,2001) ]
    = 1/2002 * [ - C(2002,0) + C(2002,1) - C(2002,2002) ]
    = 1/2002 * [ -1 + 2002 - 1 ]
    = 1000/1001

  10. Standard member royalchicken
    CHAOS GHOST!!!
    03 Feb '06 18:07
    Originally posted by psychopath42
    Let f(x) = a_1*x + a_2*x(x-1) + a_3*x(x-1)(x-2) + ... + a_2000*x(x-1)(x-2)...(x-1999)
    where
    a_k = (-1)^(k+1)/(k+1)!

    Lemma: f(x) = P(x)

    Proof of lemma:
    It suffices to show that f(n) = n/(n+1) for all integers n=0,...,2000 inclusive.
    For n=0:
    f(0) = 0 is obvious

    For n=1,...,2000:
    f(n) = a_1*n + a_2*n(n-1) + a_3*n(n-1)(n-2) + ... + a_n*n(n-1 ...[text shortened]... 02 * [ - C(2002,0) + C(2002,1) - C(2002,2002) ]
    = 1/2002 * [ -1 + 2002 - 1 ]
    = 1000/1001

    Nicely done!
  11. Standard member PBE6
    Bananarama
    03 Feb '06 18:52
    Originally posted by psychopath42
    Let f(x) = a_1*x + a_2*x(x-1) + a_3*x(x-1)(x-2) + ... + a_2000*x(x-1)(x-2)...(x-1999)
    where
    a_k = (-1)^(k+1)/(k+1)!

    Lemma: f(x) = P(x)

    Proof of lemma:
    It suffices to show that f(n) = n/(n+1) for all integers n=0,...,2000 inclusive.
    For n=0:
    f(0) = 0 is obvious

    For n=1,...,2000:
    f(n) = a_1*n + a_2*n(n-1) + a_3*n(n-1)(n-2) + ... + a_n*n(n-1 ...[text shortened]... 02 * [ - C(2002,0) + C(2002,1) - C(2002,2002) ]
    = 1/2002 * [ -1 + 2002 - 1 ]
    = 1000/1001

    Wow, you really are a psychopath. Nice job!
  12. Standard member TheMaster37
    Kupikupopo!
    04 Feb '06 13:24
    Aha, so that's the trick! Thanks for helping us out of our misery