wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> A Polynomial
        
(Message started by: THUDandBLUNDER on Dec 6^th, 2004, 10:26am)

Title: A Polynomial
Post by THUDandBLUNDER on Dec 6^th, 2004, 10:26am

Let P(x) = c_nxⁿ + c_n-1x^n-1 + ... + c₀ be a polynomial with integer coefficients.
Suppose that r is a rational number such that P(r) = 0.
Show that the n numbers c_nr, c_nr² + c_n-1r, c_nr³ + c_n-1r² + c_n-2r, ......., c_nrⁿ + c_n-1r^n-1 + ... + c₁r are integers.

Title: Re: A Polynomial
Post by Barukh on Dec 8^th, 2004, 1:26am

[smiley=blacksquare.gif][hide]
Since this problem is in Putnam section, it is possible to use heavier stuff – so I will exploit Gauss’s Polynomial Theorem (http://mathworld.wolfram.com/GausssPolynomialTheorem.html) (GPT).

Because r = p/q is a root of P(x), the latter – according to GPT – may be factored as

P(x) = (qx-p)(b_n-1x^n-1 + ... + b₀),
where all b_i-s are integers. So, we get:

c_n = b_n-1q
c_n-1 = b_n-2q - b_n-1p
…
c_i = b_i-1q - b_ip
...
c₀ = -b₀p

Now, suppose we want to evaluate P(r) using those expressions and applying Horner’s rule (http://mathworld.wolfram.com/HornersRule.html). We will get the following partial sums:

c_n = b_n-1q
c_nr + c_n-1 = b_n-2q
…
c_nrⁱ + c_n-1r^i-1 + … + c_n-i = b_n-i-1q
...
c_nr^n-1 + c_n-1r^n-2 + … + c₁ = b₀q

Note that when multiplied by r, these sums become the n requested numbers – which therefore equal b_n-1p, b_n-2p, …, b₀p, all integers.
[/hide][smiley=blacksquare.gif]

Nice problem, THUD&BLUNDER! Is it possible to know the source? ;)

Title: Re: A Polynomial
Post by THUDandBLUNDER on Dec 8^th, 2004, 7:12am

Quote:

Nice problem, THUD&BLUNDER! Is it possible to know the source?

Yes, it is possible. ;)

Title: Re: A Polynomial
Post by Barukh on Dec 8^th, 2004, 9:20am

on 12/08/04 at 07:12:58, THUDandBLUNDER wrote:

Yes, it is possible. ;)

Thanks for the answer. ;D You are in a good company:

Von Neumann was the subject of many dotty professor stories. Von Neumann supposedly had the habit of simply writing answers to homework assignments on the board (the method of solution being, of course, obvious) when he was asked how to solve problems. One time one of his students tried to get more helpful information by asking if there was another way to solve the problem. Von Neumann looked blank for a moment, thought, and then answered, "Yes."