Author |
Topic: Guess The Polynomial (Read 1889 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Guess The Polynomial
« on: Jun 26th, 2009, 10:12pm » |
 Quote  Modify
|
P(x) is a polynomial of unknown degree, with unknown nonnegative integer coefficients.
A magic genie offers to tell you the value of this polynomial at two points of your choice, in sequence. That is,
1. You choose a number u, and the genie tells you P(u).
2. Then you choose a number v, and the genie tells you P(v).
How can you use this information to determine the entire polynomial?
// edit: clarified that the guesses are made in order.
|
| « Last Edit: Jun 30th, 2009, 3:06am by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
 |
Re: Guess The Polynomial
« Reply #1 on: Jun 27th, 2009, 12:22am » |
Quote Modify
|
Given enough computation time, it should be enough to know P(pi).
Presumably there is an answer that eliminates the need for huge computations, however.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Guess The Polynomial
« Reply #2 on: Jun 27th, 2009, 12:45am » |
Quote Modify
|
on Jun 27th, 2009, 12:22am, Obob wrote:Given enough computation time, it should be enough to know P(pi).
Presumably there is an answer that eliminates the need for huge computations, however. |
|
Yes, this is exactly what I was thinking about.
... as the number of polynomials is countable, you can loop through all of them and check for the best match by comparing new value until you decide which difference is bigger.
|
|
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Guess The Polynomial
« Reply #3 on: Jun 27th, 2009, 4:55am » |
Quote Modify
|
If we get to know P(u) before we need to pick v, a much easier solution was hinted at in this thread: choose u=1 and v any integer greater than P(1); a power of ten is the most convenient choice.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Guess The Polynomial
« Reply #4 on: Jun 27th, 2009, 9:51am » |
Quote Modify
|
on Jun 27th, 2009, 12:45am, Hippo wrote:
Yes, this is exactly what I was thinking about.
... as the number of polynomials is countable, you can loop through all of them and check for the best match by comparing new value until you decide which difference is bigger. |
|
It's not enough that there are only countably many possibilities though, since checking equality of reals is only semi-decidable. E.g., if P( ) = 1.000000000000000000000000..., did he pick P(x) = 1 or
P(x) = 909474452321624805685314 x - 2857198258041217165097342?
But the fact that the coefficients are nonnegative means you can reject all but one possibility with a finite amount of work.
Well I suppose it depends on how he tells you P(), but being able to query any given digit is a reasonable interpretation. Maybe he gives you an answer like:
"+ (the smallest counterexample to Goldbach's conjecture if it exists; otherwise, the Ramsey number R(17,42))."
|
| « Last Edit: Jun 27th, 2009, 10:05am by Eigenray » |
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Guess The Polynomial
« Reply #5 on: Jun 27th, 2009, 11:44am » |
Quote Modify
|
Ah yes, pex's solution is much nicer from a computational standpoint, provided you get to know the answer to the first question before asking the second.
If you had an insanely fast computer capable of real number arithmetic, then the P(pi) solution works since pi is transcendental. The actual computation time is completely infeasible, however. Furthermore, the P(pi) solution doesn't require knowing the coefficients are positive integers; it would be enough to know that they lie in some countable extension field of the rationals.
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Guess The Polynomial
« Reply #6 on: Jun 28th, 2009, 6:11pm » |
Quote Modify
|
Nice pex; yes, the original intention was that you can receive the evaluation P(x1) before guessing x2. I will specify this in the problem. I hadn't thought about P(pi) ... perhaps I should add "efficient" to the problem statement ...
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Guess The Polynomial
« Reply #7 on: Jun 29th, 2009, 2:15am » |
Quote Modify
|
Still an interesting puzzle, but I can't take credit for the nice solution - I'll just link it again to be sure.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print