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.
Search
A polynomial of degree n would require n+1 inputs.
Agreed, but there you are allowing the coefficients to be real valued. Moreover, you do not know what the order/degree (n) of the polynomial is. Thus saying (n+1) inputs isn't an answer and therefore is incorrect.
Well, at this point, the problem is above my pay grade. Looking forward to a solution.
I think I can reveal that the answer is 2. Can anyone still give me a method of guessing the polynomial with 2 inputs?
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.
This was the same point brought up by Ian Fowler, but I'll reiterate. The difference, in this case, is that I am saying that the coefficients are not real-valued. This helps reduce the complexity of the problem. You are provided with the information that the coefficients are positive integers, that is what reduces, the answer from infinity to 2. In addition to the above, I am not saying that picking any arbitrary 2 points will have all the information about the polynomial (though it might have, am not sure), but if we "intelligently" pick two input points, we can definitely know the whole polynomial.
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.
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.