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.
To see this working, head to your live site.
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.
@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.
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.