Author |
Topic: A Polynomial (Read 632 times) |
|
ThudnBlunder
Uberpuzzler
The dewdrop slides into the shining Sea
Gender: 
Posts: 4489
|
 |
A Polynomial
« on: Dec 6th, 2004, 10:26am » |
 Quote  Modify
|
Let P(x) = cnxn + cn-1xn-1 + ... + c0 be a polynomial with integer coefficients.
Suppose that r is a rational number such that P(r) = 0.
Show that the n numbers cnr, cnr2 + cn-1r, cnr3 + cn-1r2 + cn-2r, ......., cnrn + cn-1rn-1 + ... + c1r are integers.
|
| « Last Edit: Dec 6th, 2004, 10:27am by ThudnBlunder » |
 IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: A Polynomial
« Reply #1 on: Dec 8th, 2004, 1:26am » |
Quote Modify
|
[smiley=blacksquare.gif]
Since this problem is in Putnam section, it is possible to use heavier stuff – so I will exploit Gauss’s Polynomial Theorem (GPT).
Because r = p/q is a root of P(x), the latter – according to GPT – may be factored as
P(x) = (qx-p)(bn-1xn-1 + ... + b0),
where all bi-s are integers. So, we get:
cn = bn-1q
cn-1 = bn-2q - bn-1p
…
ci = bi-1q - bip
...
c0 = -b0p
Now, suppose we want to evaluate P(r) using those expressions and applying Horner’s rule. We will get the following partial sums:
cn = bn-1q
cnr + cn-1 = bn-2q
…
cnri + cn-1ri-1 + … + cn-i = bn-i-1q
...
cnrn-1 + cn-1rn-2 + … + c1 = b0q
Note that when multiplied by r, these sums become the n requested numbers – which therefore equal bn-1p, bn-2p, …, b0p, all integers.
[smiley=blacksquare.gif]
Nice problem, THUD&BLUNDER! Is it possible to know the source? 
|
|
IP Logged |
|
|
|
ThudnBlunder
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: A Polynomial
« Reply #2 on: Dec 8th, 2004, 7:12am » |
Quote Modify
|
Quote:| Nice problem, THUD&BLUNDER! Is it possible to know the source? |
|
Yes, it is possible.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: A Polynomial
« Reply #3 on: Dec 8th, 2004, 9:20am » |
Quote Modify
|
on Dec 8th, 2004, 7:12am, THUDandBLUNDER wrote:| Yes, it is possible. |
|
Thanks for the answer.  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."
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print