0
$\begingroup$

A friend of us makes up a polynomial with nonnegative integer coefficients. Our task is to find it out with a minimum number of queries. For each query we give him a nonnegative integer L and he computes P(L) and returns the result to us.

I know the beautiful trick to solve this - first ask P(1) to determine the sum of the coefficients that is at least as great as the greatest coefficent of the polynomial. Let T be the result of P(1). Then we ask P(T + 1). The value we get we covert to T + 1-base positional system and this way we figure the coefficients of the polynomial in 2 queries. I was wondering if it is possible to find it with a single querie or 2 queries is the lower bound of the worst case?

$\endgroup$
1
  • $\begingroup$ It is impossible to get it in one query. Notice, for example, that for any number that you pick to evaluate, there are an infinite number of polynomials that pass thru that point. If the point is $c$ then every polynomial multiple of $(x-c)$ is a candidate. $\endgroup$ – Phicar Mar 21 '20 at 0:24
0
$\begingroup$

I would say that for a n-th degree polynomial, you'd need at most n+1 queries to solve it. This is because every polynomial of degree n has n+1 variables and this is solvable if you have n+1 equations (that are linearly independent).

$\endgroup$
0
$\begingroup$

You give your friend the number $\pi$. A polynomial with integer coefficients is completely determined by its value at $\pi$. Of course, any transcendental would do, in place of $\pi$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.