wu :: forums - Print Page


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

        riddles >> medium >> Guess The Polynomial
        
(Message started by: william wu on Jun 26^th, 2009, 10:12pm)

Title: Guess The Polynomial
Post by william wu on Jun 26^th, 2009, 10:12pm

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.

Title: Re: Guess The Polynomial
Post by Obob on Jun 27^th, 2009, 12:22am

[hide]Given enough computation time, it should be enough to know P(pi).[/hide]

Presumably there is an answer that eliminates the need for huge computations, however.

Title: Re: Guess The Polynomial
Post by Hippo on Jun 27^th, 2009, 12:45am

on 06/27/09 at 00:22:56, Obob wrote:

[hide]Given enough computation time, it should be enough to know P(pi).[/hide]

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.

Title: Re: Guess The Polynomial
Post by pex on Jun 27^th, 2009, 4:55am

If we get to know P(u) before we need to pick v, a much easier solution was hinted at in this thread (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_easy;action=display;num=1127394402): [hide]choose u=1 and v any integer greater than P(1); a power of ten is the most convenient choice.[/hide]

Title: Re: Guess The Polynomial
Post by Eigenray on Jun 27^th, 2009, 9:51am

on 06/27/09 at 00:45:49, Hippo wrote:

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(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif) = 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(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif), but being able to query any given digit is a reasonable interpretation. Maybe he gives you an answer like:
"http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif+ (the smallest counterexample to Goldbach's conjecture if it exists; otherwise, the Ramsey number R(17,42))."

Title: Re: Guess The Polynomial
Post by Obob on Jun 27^th, 2009, 11:44am

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.

Title: Re: Guess The Polynomial
Post by william wu on Jun 28^th, 2009, 6:11pm

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 ...

Title: Re: Guess The Polynomial
Post by pex on Jun 29^th, 2009, 2:15am

Still an interesting puzzle, but I can't take credit for the nice solution - I'll just link it again (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_easy;action=display;num=1127394402) to be sure.