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.
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.
@Digo Sen
Well, at this point, the problem is above my pay grade. Looking forward to a solution.
@Ian Fowler I don't know how many people are trying out this problem so I'm not sure when to release the solution. If quite a few people ask for the solution, then I'll post it.
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.
@Digo Sen This problem is so damn cool! And at this point (no pun intended), I can't imagine how to, as you say, intelligently pick the 2 input values. I have thought more about it and it seems that I am missing something fundamental - the integer co-efficients are the key. Can you give me a clue as to what type of values you would use as the 2 input values x without giving away what they actually are and what type of value P(x) returns? If this gives away too much, then don't answer yet. Thanks again - Ian
@Ian Fowler If you haven't tried to check out possible "guesses" with examples, then that is the first thing that you should do. Take a few Polynomials, and see what sort of input would give you a number which would in essence give away the whole Polynomial. A good example would be x^2+3x+5, what sort of i/p would reveal everything that characterizes the Polynomial.