blackpenredpen

math for fun 

To see this working, head to your live site.
  • Categories
  • All Posts
  • My Posts
Digo Sen
Oct 30, 2019
  ·  Edited: Oct 30, 2019

Guess the Polynomial

in Math Problems

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.

10 comments
Ian Fowler
Oct 30, 2019

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

0
Digo Sen
Oct 30, 2019

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.

0
Ian Fowler
Oct 30, 2019

@Digo Sen

Well, at this point, the problem is above my pay grade. Looking forward to a solution.

0
Digo Sen
Oct 30, 2019

@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.

0
Digo Sen
Nov 01, 2019

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

0
Alavi ULLAH
Nov 06, 2019

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.

0
Digo Sen
Nov 06, 2019

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.

0
Ian Fowler
Nov 06, 2019

@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

0
Digo Sen
Nov 06, 2019

@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.