Alice has a secret polynomial $P$ with positive integer coefficients. When Bob gives Alice a positive integer $n \neq 2016$, Alice replies with the value of $P(n)$. After doing this several times, Bob guesses the value of $P(2016)$; he wins if he is correct and loses if not.

How can Bob guarantee a win in as few such exchanges as possible?

  • $\begingroup$ Well, asking for P(0) will give him he value of the constant, then asking for P(1) will give him the sum of the coefficients and the constant. I'm still working on how to figure out the degree of the polynomial. $\endgroup$
    – tinezekis
    Jan 29, 2016 at 17:30
  • 1
    $\begingroup$ Note that if the coefficients could be arbitrary rational numbers, Bob would never be able to guess the polynomial for any number of questions. This is because we can always find a polynomial of degree $n-1$ that goes through a set of $n$ points in the $xy$-plane (assuming that they all have distinct $x$-values.) So the solution must have something to do with a special property of the integers (prime factorization?) $\endgroup$ Jan 29, 2016 at 22:37
  • 1
    $\begingroup$ @caonayemi: 0 is not usually considered to be a "positive integer", so if we take the question as written, Bob can't ask for $P(0)$. $\endgroup$ Jan 29, 2016 at 22:44
  • $\begingroup$ Thanks, @MichaelSeifert; I missed that limitation on n when I read the question. $\endgroup$
    – tinezekis
    Jan 30, 2016 at 1:22
  • 1
    $\begingroup$ @MichaelSeifert Now I have found a proof that the given solution is optimal. But this comment field is too small to contain it. $\endgroup$
    – kasperd
    Feb 1, 2016 at 18:51

3 Answers 3


Bob can get it in

2 questions.

Here's how:

First guess 1. Then guess a power of 10 greater than the response; he can simply "read off" the coefficients. That uniquely determines the polynomial, so he can just calculate $P(2016)$ for his final answer.

What I mean by the term in quotes:

I'll use the polynomial $17x^4 + 4x^3 + 5x^2 + 8$ as an example: $f(1) = 34$, so I choose any power of ten greater than 34. I pick 1000. $f(1000) = 17004005000008$, and you can easily see the coefficients there, separated by zeroes. (Chunk starting from the right in groups of $n$, where $10^n$ is the number you picked.)

  • 6
    $\begingroup$ I didn't understand what you meant by "read off" the coefficients, but then I tried it with a couple of polynomials. Good work! $\endgroup$
    – tinezekis
    Jan 29, 2016 at 17:34
  • 4
    $\begingroup$ @Deusovi Chunking like that only works for reasonably small coefficients. Consider $17x^4 + 400x^3 + 5x^2 + 8$. $P(1) = 430$ and $P(1000) = 17400005000008$. The coefficients are present in the right order, but the parsing is a little bit busted. $\endgroup$
    – Matt
    Jan 29, 2016 at 18:22
  • 5
    $\begingroup$ @Matt: Slight modification: Chunk in groups of $n$ digits starting from the right. $\endgroup$
    – Deusovi
    Jan 29, 2016 at 18:56
  • 9
    $\begingroup$ Effectively, you're exploiting the fact that for any two integers $N, M$, there is a unique decomposition of $N$ of the form $N = a_0 + a_1 M + a_2 M^2 + \dots + a_N M^N$ with all $a_i < M$. (In other words, $N$ has a unique representation in base $M$.) This means that any integer $M > P(1)$ will do the trick: the digits of $N = P(M)$, when expressed in base $M$, will be the coefficients of the polynomial. (Choosing $M$ to be a power of 10 just makes it easier to read off the digits when we express $N$ in base 10.) $\endgroup$ Jan 29, 2016 at 22:59
  • 6
    $\begingroup$ @Michael: Exactly. If we chose our second guess to be a base bigger than $P(1)$, we could just read off single digits in that base. I just didn't want to complicate things with base conversion. $\endgroup$
    – Deusovi
    Jan 30, 2016 at 4:58

If we allow Bob to ask for values not at positive integers, he can find $P(2016)$ with just one question. He asks for $P(\pi)$ and tells Alice to give him the integral part, then pause until he says start, then keep outputting decimal digits until he says stop. There are only finitely many monomials with values less than this at $\pi$. They can be combined in finitely many ways. He makes a finite list of all the polynomials that produce a value of $P(\pi)$ between the integral part Alice said and $1$ more and computes the decimal expansions until every one differs from the rest. He then asks Alice to start giving him decimals and tells her to stop when he knows the polynomial.

For example, if $100 \le P(\pi) \lt 101$, he can only use constants $1$ through $100$, linear terms $x$ through $31x$, quadratics $x^2$ through $9x^2$, cubics $x^3$ through $4x^3$ and $x^4$. Most combinations of those will be too large, but $97+x$ evaluates to $100.14159$, $x^3+4x^2+60$ evaluates to $100.615$and $x^3+4x^2+x^2+x+27$ to $100.6263$. I don't know how close they can be, but it won't take too many decimals to sort it out.


Post-script. Jared is right and I didn't read the conditions correctly. I missed that the coefficients have to be positive. What I wrote below is rubbish.

He can't. Let S = {s1, s2, ... sn} be the set of numbers on which he could choose to sample P(x) so he will know the values P(s1), P(s2), ... P(sn). Now define the polynomial MV(x) as Product all i in S except V (x-i) so now MV(x) is zero everywhere in S but non-zero at x=V. (The value at V is probably quite large)

Alice now chooses a random polynomial Q(x) and a random integer R and adds P(x) and R.M2016(x) to get P(x).

When Bob samples P(x) he gets the values of Q(x) because M2016(x) is zero on all his sample points. He doesn't know R so he can't work out the value P(2016) = Q(2016)+R.M2016(2016)

The answer that has been accepted above uses Q(x) = 17x4 + 4x3 + 5x2 + 8 as an example but P(x) = Q(x) + (x-1)(x-1000) takes exactly the same values at the sample-points of 1 and 1000.

  • 6
    $\begingroup$ …but then P(x) doesn't have positive integer coefficients. $\endgroup$
    – Jared
    Jan 31, 2016 at 13:24
  • $\begingroup$ Whoops, my bad. I don't know if my objection is salvageable $\endgroup$ Jan 31, 2016 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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