Find the coefficients of the polynomial of degree 2017!

[Steven G]

The polynomial p(x) is of degree 2017 and has non-negative integer coefficients which you don't know.

If you input a value like x=x_0, the computer will output the value p(x₀) at a cost of $1($2.25 for Denis).

If you want to determine all 2018 coefficients of p(x) at a minimum cost using only positive integer inputs, what is your cost in dollars?

 

[Steven G]

The polynomial p(x) is of degree 2017 and has non-negative integer coefficients which you don't know.

If you input a value like x=x_0, the computer will output the value p(x₀) at a cost of $1($2.25 for Denis).

If you want to determine all 2018 coefficients of p(x) at a minimum cost using only positive integer inputs, what is your cost in dollars?

Well since nobody replied I will give the answer. The answer is $2

First you input x₀=1 and the computer would give you p(1), which is the sum of all coefficents.
let s=p(1)


Then you input x₁= s+1, and the computer would give you p(s+1)


Converting p(s+1) to base s+1 and the digits correspond to the coefficients of p(x)

Because p(s+1) = d₂₀₁₇(s+1)²⁰¹⁷ + d₂₀₁₆(s+1)²⁰¹⁶ + ... +d₀

is exactly how we represent integers in base s+1


we use s=p(1) to make sure that the second number we input is larger than any of the coefficients.




For example, suppose the polynomial is 5x²+3x+4


First, we set an input of x=1 and get 5+3+4 = 12


Now, we input that sum plus one, that is, x=13. 5(13)²+3(13)+4=888


888 converted to base 13 is 534 which is the coefficients we want.

This is because if we backtrack and consider the meaning of 534 base 13, it's


4 copies of 1

3 copies of 13


5 copies of 13²

that is, exactly 5(13)²+3(13)+4

Compare this with the given solution and it should become clearer. Note since our base is always larger than the sum of the coefficients, it will always be possible to represent all coefficients as single digits.

 

[Dr.Peterson]

Do you have a proof that the polynomial you get this way is the only one that fits the conditions?

In your quadratic example, I believe it is; quadratics are determined by three points, and the conditions on the coefficients make up for having only two, at least in this one case. But can you try a cubic example and show that there is only one solution given p(1) and p(s+1)?

Then, can you show this is true for degree 2017?

Without that, you haven't solved the puzzle yet. You are claiming to determine all the coefficients, which means being certain that your answer is the only one.

 

[Steven G]

Do you have a proof that the polynomial you get this way is the only one that fits the conditions?

In your quadratic example, I believe it is; quadratics are determined by three points, and the conditions on the coefficients make up for having only two, at least in this one case. But can you try a cubic example and show that there is only one solution given p(1) and p(s+1)?

Then, can you show this is true for degree 2017?

Without that, you haven't solved the puzzle yet. You are claiming to determine all the coefficients, which means being certain that your answer is the only one.

Let p(x) = 2x³+4x²+4, So p(1)=10, that is s=10 and s+1=11. Now p(11) = 2662+484+4 = 3150. Now 3150 in base 11 is 2404. as 2(11³) + 4(11²) + 0(11) +4(1) = 2662 + 484 + 4 = 3150

 

[Dr.Peterson]

Let p(x) = 2x³+4x²+4, So p(1)=10, that is s=10 and s+1=11. Now p(11) = 2662+484+4 = 3150. Now 3150 in base 11 is 2404. as 2(11³) + 4(11²) + 0(11) +4(1) = 2662 + 484 + 4 = 3150

That doesn't touch my question. Can you prove that for any cubic (and, eventually, for any polynomial of any degree) your procedure produces the ONLY polynomial with non-negative integer coefficients with the two function values you asked for? All you've shown is that in one example it produces the answer you wanted, not that there is no case where another polynomial would produce the same values.

It's entirely possible that you are right; but you have to prove it before you can claim that your solution is valid.

 

[Steven G]

That doesn't touch my question. Can you prove that for any cubic (and, eventually, for any polynomial of any degree) your procedure produces the ONLY polynomial with non-negative integer coefficients with the two function values you asked for? All you've shown is that in one example it produces the answer you wanted, not that there is no case where another polynomial would produce the same values.

It's entirely possible that you are right; but you have to prove it before you can claim that your solution is valid.

Let P(x)= ax³+bx²+cx+d where all coefficients are non negative.

P(1) = a+b+c+d = k. P(k+1) = a(k+1)³+b(k+1)² +c(k+1)+ d. Clearly P(k+1) in base k+1 = a(k+1)³+b(k+1)² +c(k+1)+ d since a,b,c and d are less than k+1. But the number P(k+1) in base k+1 are the coefficients of P(x).

Is this what you want?

 

[Dr.Peterson]

Let P(x)= ax³+bx²+cx+d where all coefficients are non negative.

P(1) = a+b+c+d = k. P(k+1) = a(k+1)³+b(k+1)² +c(k+1)+ d. Clearly P(k+1) in base k+1 = a(k+1)³+b(k+1)² +c(k+1)+ d since a,b,c and d are less than k+1. But the number P(k+1) in base k+1 are the coefficients of P(x).

Is this what you want?

I suppose it's all there, and does extend to any degree. I've just been bothered that you aren't explicitly showing that no other polynomial could have the same two values, though that is implied when I think about it.

Maybe I need it stated more like this: Suppose that the unknown polynomial is P(x)= ax³+bx²+cx+d. If k = P(1) = a+b+c+d, and we ask for P(k+1) = a(k+1)³+b(k+1)² +c(k+1)+ d, then because a, b, c, and d are non-negative integers less than k+1, they must be the digits of P(k+1) written in base k+1, because any positive integer has a unique representation in a given base.

I guess some detail in your original version led me off in a wrong direction.