Cool Thing

[stupidityismygam]

Given a polynomial with non-negative integer coefficients, what is the minimum number of evaluations at integer values of [unparseable or potentially dangerous latex formula] (such as [unparseable or potentially dangerous latex formula]) must you have in order to uniquely determine the polynomial.

[klebian]

Is it not just whatever degree the polynomial is of? Without really thinking about this, it seems to me like an n-th degree polynomial can seem to be like a (n-1)-th polynomial with just n-1 "evaluations"

[Kenon]

From some thought I would assume it is 3 (assuming the answer does not involve n, in which case it's totally n+1), but I have no proof at the moment. The thought comes down to evaluating at x=0, x=1, and x=2. Then you take f(1)-f(0) and that expresses the total value of the coefficients added together (aside from the non-x integer). I'll write more on the idea later.

[stupidityismygam]

[stupidityismygam]

[shrig94]

Lagrange Interpoolation

[stupidityismygam]

To get responses back up, the answer is 2. Any ideas of how to go about finding the polynomial?

[AuSmith]

Ha, I first thought, "why not just evaluate at your favorite transcendental number..."

Well, we already know that positive integers return positive values. Since we already know information about those, it seems more informative to evaluate at negative integers. Indeed, evaluating the polynomial [unparseable or potentially dangerous latex formula] at a positive integer [unparseable or potentially dangerous latex formula] can only be as good as evaluating at [unparseable or potentially dangerous latex formula] because we may create a new polynomial of the same degree that has nonnegative coefficients: [unparseable or potentially dangerous latex formula].

So, we're not given the degree of the polynomial, are we?

[stupidityismygam]

[AuSmith]

[stupidityismygam]

[AuSmith]

It was more of a puzzle this way! At least, it looked impossible otherwise...

[AuSmith]

Call [unparseable or potentially dangerous latex formula]

1) First, we want to find an upper bound for the coefficients. Realizing that

[unparseable or potentially dangerous latex formula]

for all [unparseable or potentially dangerous latex formula] (because [unparseable or potentially dangerous latex formula]), we have a bound. This is our first evaluation.

2) Call [unparseable or potentially dangerous latex formula]. We now determine the polynomial from the value [unparseable or potentially dangerous latex formula].

[unparseable or potentially dangerous latex formula]

Then, once we know [unparseable or potentially dangerous latex formula], call

[unparseable or potentially dangerous latex formula],

a new polynomial that we can do the same trick on and get its constant coefficient, [unparseable or potentially dangerous latex formula],

[unparseable or potentially dangerous latex formula].

By method of finite descent, we uniquely determine the polynomial.


Neat problem, Stephen - is it yours?

[stupidityismygam]

Not mine, someone at my school asked me.

My solution is something along these lines:

Evaluate at [unparseable or potentially dangerous latex formula]. This gives an upper bound of the coefficients. Then, evaluate at [unparseable or potentially dangerous latex formula] and express the result in base [unparseable or potentially dangerous latex formula]. The number will read out the coefficients of the polynomial.