Author |
Topic: A Polynomial Mystery (Read 1382 times) |
|
inexorable
Full Member
Posts: 211
|
 |
A Polynomial Mystery
« on: Nov 1st, 2005, 12:10am » |
 Quote  Modify
|
Alice: I'm thinking of a polynomial with nonnegative integer coefficients. Can you tell me what it is?
Bob: Well, I need more info than that. Can I ask you for some values of the polynomial?
Alice: That seems reasonable. How many would you like?
Bob: Well, N + 1 would be nice, where N is the degree of your polynomial, for then I could just solve N + 1 equations in N + 1 unknowns.
Alice: That would take too long, both for me and for you. Moreover, you don't know the degree and I don't want to reveal it. But I am willing to tell you two values of the polynomial for integer arguments that you choose.
Can Bob determine Alice's polynomial P(x) asking Alice only twice for integer values of P(x)?
|
|
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 7527
|
|
Re: A Polynomial Mystery
« Reply #1 on: Nov 1st, 2005, 1:10am » |
Quote Modify
|
The answer is : yes.
If it were not, you wouldn't post the question here, would you?
So the real question is: how?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A Polynomial Mystery
« Reply #2 on: Nov 1st, 2005, 1:32am » |
Quote Modify
|
I'm almost positive the same question came up before, but I can't for the life of me find it..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: A Polynomial Mystery
« Reply #3 on: Nov 1st, 2005, 2:07am » |
Quote Modify
|
Here: click!
|
|
IP Logged |
|
|
|
dot star
Guest
|
can anyone please explain me how is it possible by knowing the value P(x) for two values of x?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A Polynomial Mystery
« Reply #5 on: Nov 1st, 2005, 7:59am » |
Quote Modify
|
It has to do with the fact that all coefficients or nonnegative. It's a lot more restrictive than it seems.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
inexorable
Full Member
Posts: 211
|
|
Re: A Polynomial Mystery
« Reply #6 on: Nov 1st, 2005, 8:36am » |
Quote Modify
|
ok here's the solution
Since all of the coefficients are nonnegative integers, P(1) is at least as big as the largest coefficient. Then P(k) for large enough k gives an answer which, in base k, the coefficients are listed. Note k could be as small as P(1) + 1, or more easily as the next power of 10 for easy calculation. 
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove