wu :: forums - Print Page


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

        riddles >> easy >> Predict the polynomial
        
(Message started by: Neelesh on Sep 22^nd, 2005, 6:06am)

Title: Predict the polynomial
Post by Neelesh on Sep 22^nd, 2005, 6:06am

I have a polynomial P(x) with non-negative integral coefficients. You have to guess the polynomial. To do that you can ask me the value of polynomial for various values of x.

How many 'x' s you need so that you can determine the polynomial accurately?

Note that you donot know the degree of the polynomial in advance

[hide] however, you know that all coefficients are non-negative integers [/hide]

Title: Re: Predict the polynomial
Post by Barukh on Sep 26^th, 2005, 5:11am

That's an interesting question!

[hideb]If an upper bound for the coefficients is known, one question suffices. Otherwise, n+2 questions are probably needed for the n-degree polynomial[/hideb]

Title: Re: Predict the polynomial
Post by Neelesh on Sep 26^th, 2005, 5:26am

An upper bound for coefficients is not known in advance.

[hideb]However, you can find the upper bound in one attempt

That means we need total two values of x. [/hideb]

Title: Re: Predict the polynomial
Post by Barukh on Sep 26^th, 2005, 5:34am

Correct! How stupid of me!

And what a nice problem, Neelesh! :D