5
$\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 coefficient of the polynomial. Let $T$ be the result of $P(1)$. Then we ask $P(T + 1)$. The value we get we convert to a $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 query or 2 queries is the lower bound of the worst case?

$\endgroup$
3
$\begingroup$

It's not possible to find it with a single query.

Suppose you had one, e.g. asking for a single number $n$. Then you can't distinguish between the cases where your friend's secret polynomial is $P(x) = 2x$ and $P(x) = x + n$; in both cases, they will reply with $2n$. (I know it's unlikely that he chose the second option, especially if $n$ is a non-obvious number like 372, but you can't rule it out.)

| improve this answer | |
$\endgroup$
  • $\begingroup$ "number" doesn't necessarily mean "integer". $\endgroup$ – Rand al'Thor Mar 21 at 15:38
7
$\begingroup$

If this is allowed you could ask him to evaluate the polynomial at $\pi$ or another transcendental number.

The response will be something like $a_0 + a_1 \pi + a_2 \pi^2 + ...$, which is unique for all combinations of $\{a_i\}$, even for negative integers (by the definiton of transcendental numbers). The drawback of this method is just that depending on the format of the returned number it might be hard to decompose it.

| improve this answer | |
$\endgroup$
  • 5
    $\begingroup$ It's not enough just for the integer powers to be irrational numbers; you need to be sure there's no rational relation between them. $\pi$ does work, but the term you're looking for is transcendental. $\endgroup$ – Rand al'Thor Mar 21 at 15:38
  • $\begingroup$ @Randal'Thor Thanks, I didn't know that transcendental numbers are actually defined by this property. I've added it to the answer. $\endgroup$ – A. P. Mar 21 at 15:44

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.