There is a computer that generates a polynomial P(x) of arbitrary degree and positive integer coefficients. You are only allowed to enter inputs for the polynomial P(x) into the computer; the computer will print out the result. So if 2 is your input, the computer prints out the numeric value P(2). This is a theoretical computer and thus numerical accuracy is not something to worry about. What is the minimum no. of inputs before you can completely determine the Polynomial. It goes without saying that the answer is a finite no.

top of page

bottom of page

Okay, so I'll post the solution. Its been quite a while since I posted the question and I don't see the point in delaying. @Ian Fowler and @Alavi ULLAH , If you need time to figure it out then this is your SPOILER WARNING.

If the Polynomial in question was P(x)=2x^2+3x+5, then P(10) would give us 235 which happen to be the coefficients of the polynomial. Similarly, if P(x) was 2x^5+3x^3+2x+1, then P(10) would be 203021; and in order to find the coefficients, we need to perform repeated division by 10 and find the remainder every time. Since the number is finite, the process of repeated division will stop when the quotient gets to 0. The sequence of remainders so obtained will be 1, 2, 0, 3, 0, 2 which are exactly the coefficients of the Polynomial. The problem with this method, is that if P(x) was 2x^2+35x+5, then P(10) would be 555, which is not representative of the coefficients of the original polynomial. However, if we plug in x=100, then P(100) would give you 23505. Now perform repeated division by 100 and find the remainder every time (5 then 35 then 2). Note that x=100 also works for P(x)=2x^2+3x+5. In general you need to put in 10^n where n is at least as large as the largest coefficient in P(x). Now one thing that we do know is that since the coefficients of P(x) are positive integers, the sum of all the coefficients (P(1)) is larger than each of the individual coefficients. Now for any no. greater than 1, its numeric value is greater than its number of digits. Putting it all together we have P(1) is greater than the number of digits of all the coefficients of P(x). Thus all you need to do is evaluate P(1) then evaluate P(10^{P(1)}); repeatedly divide the output of the latter by 10^{P(1)} and collect the remainder till you get 0 as the quotient.

If you understand the above process, then its not hard to see that the process need not be restricted to 10, 10 gives you a nice visual description of the thinking process. In fact you could plug in P(7^{P(1)}) and perform repeated division by 7^{P(1)} and collect the remainder.

What? Maybe I'm not understanding something here but shouldn't the answer be infinity? There are a bunch of polynomials that pass through the points (x1,y1) and (x2,y2) so two points isn't enough to know for sure which polynomial it is.

I think I can reveal that the answer is 2. Can anyone still give me a method of guessing the polynomial with 2 inputs?

A polynomial of degree n would require n+1 inputs.