A Polynomial Black Box
The polynomial is of degree 2017 and has non-negative integer coefficients which you don't know.
If you input a value like the computer will output the value at a cost of $1.
If you want to determine all 2018 coefficients of at a minimum cost using only positive integer inputs, what is your cost in dollars?
The answer is 2.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
3 solutions
Moderator note:
There is some confusion in the comments as to what is going on, so a practical example using 2 as the degree rather than 2017 might help.
Suppose the polynomial is
First, we set an input of and get
Now, we input that sum plus one, that is,
converted to base 13 is which is the coefficients we want.
This is because if we backtrack and consider the meaning of base 13, it's
copies of
copies of
copies of
that is, exactly
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.
There's also the question of proving it isn't possible to do in 1 check.
Assume $1 is possible. Say that we tested with Then, we just need to find 2 polynomials and which satisfy
in which case we are unable to differentiate between these 2 polynomials.
One example is and
Here is how you determine all 2 0 1 8 coefficients.
First you input x 0 = 1 and the computer would give you p ( 1 ) , which is the sum of all coefficents.
let s = p ( 1 )
Then you input x 1 = 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 2 0 1 7 ( s + 1 ) 2 0 1 7 + d 2 0 1 6 ( s + 1 ) 2 0 1 6 + ⋯ + d 2 ( s + 1 ) 2 + d 1 ( s + 1 ) + d 0
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.
This works for p ( x ) of arbitrary degrees, as long as all coefficient are nonnegative integers.