wu :: forums - Print Page


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

        riddles >> hard >> A Polynomial Mystery
        
(Message started by: inexorable on Nov 1^st, 2005, 12:10am)

Title: A Polynomial Mystery
Post by inexorable on Nov 1^st, 2005, 12:10am

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)?

Title: Re: A Polynomial Mystery
Post by Grimbal on Nov 1^st, 2005, 1:10am

The answer is : yes.

If it were not, you wouldn't post the question here, would you?

So the real question is: how?

Title: Re: A Polynomial Mystery
Post by towr on Nov 1^st, 2005, 1:32am

I'm almost positive the same question came up before, but I can't for the life of me find it..

Title: Re: A Polynomial Mystery
Post by Grimbal on Nov 1^st, 2005, 2:07am

Here: click! (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_easy;action=display;num=1127394402)

Title: Re: A Polynomial Mystery
Post by dot star on Nov 1^st, 2005, 7:12am

can anyone please explain me how is it possible by knowing the value P(x) for two values of x?

Title: Re: A Polynomial Mystery
Post by towr on Nov 1^st, 2005, 7:59am

It has to do with the fact that all coefficients or nonnegative. It's a lot more restrictive than it seems.

Title: Re: A Polynomial Mystery
Post by inexorable on Nov 1^st, 2005, 8:36am

ok here's the solution
[hide] 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.[/hide] ;)