78

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?

boboquack
  • 21,982
  • 1
  • 66
  • 138
rnaylor
  • 2,611
  • 1
  • 15
  • 25
  • 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. – tinezekis Jan 29 '16 at 17:30
  • 1
    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?) – Michael Seifert Jan 29 '16 at 22:37
  • 1
    @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)$. – Michael Seifert Jan 29 '16 at 22:44
  • Thanks, @MichaelSeifert; I missed that limitation on n when I read the question. – tinezekis Jan 30 '16 at 01:22
  • Is zero a permissible coefficient? Since it says positive, I assume not. Then how about the polynomial $P(n) = n^2$? Since the 0th and 1st degree coefficients are zero, that would not be a valid polynomial. Or is the polynomial allowed to skip some degrees (which is just another way to say that some of the coefficients may be zero)? – kasperd Jan 30 '16 at 18:43
  • @kasperd: The solution outlined by Deusovi below works for polynomials that happen to have some coefficients equal to zero as well. The polynomial coefficients just have to be non-negative for his method to work. – Michael Seifert Feb 01 '16 at 18:31
  • @MichaelSeifert True. I am just wondering whether that method is optimal. I think it is optimal but my first attempt to show it to be optimal got stuck on not knowing whether zero coefficients are permitted or not. – kasperd Feb 01 '16 at 18:46
  • 1
    @MichaelSeifert Now I have found a proof that the given solution is optimal. But this comment field is too small to contain it. – kasperd Feb 01 '16 at 18:51
  • Related: http://math.stackexchange.com/questions/446130/quickest-way-to-determine-a-polynomial-with-positive-integer-coefficients – Watson Aug 23 '16 at 13:56

3 Answers3

112

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.)

Deusovi
  • 146,248
  • 16
  • 519
  • 609
  • 6
    I didn't understand what you meant by "read off" the coefficients, but then I tried it with a couple of polynomials. Good work! – tinezekis Jan 29 '16 at 17:34
  • 2
    @cal I added an example that hopefully makes it more clear. – Deusovi Jan 29 '16 at 17:39
  • Doesn't always work. Consider the polynomial $17x^4 + 4x^3 + 5x^2 -26$. edit: whoops didn't read positive coeffs – Steve Cox Jan 29 '16 at 17:54
  • 1
    What if a coefficient contains a zero, say 10x? How many zeroes should be removed as separators? – Lennart - Slava Ukraini Jan 29 '16 at 17:56
  • 1
    @Lennart: After the first coefficient, read off in chunks of $n$, where $10^n$ is the power you chose. Zeroes will stay zeroes. (That's why I chose an example with a zero coefficient.) In any case, the problem guarantees positive coefficients. – Deusovi Jan 29 '16 at 18:16
  • 4
    @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. – Matt Jan 29 '16 at 18:22
  • 2
    The problem is that what if I choose 10 and 100 as coefficient! (you may also choose more than 2 coefficients like 5 10s and 5 100 with 10 coefficient values for a polynom) $p(x)=100x^3+10x^2+99$ and P(1000) = 100010000099 and P(1)=209. So which one is 100 and which one is 10? – Oray Jan 29 '16 at 18:34
  • 5
    @Matt: Slight modification: Chunk in groups of $n$ digits starting from the right. – Deusovi Jan 29 '16 at 18:56
  • 3
    @Oray: Chunk in groups of $n$ digits starting from the right. – Deusovi Jan 29 '16 at 18:56
  • 9
    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.) – Michael Seifert Jan 29 '16 at 22:59
  • @Oray Also you can try each out. 10x^3 + 100x^2 + 99 doesn't give the same outputs for P(1000). – Dason Jan 30 '16 at 01:00
  • 6
    @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. – Deusovi Jan 30 '16 at 04:58
20

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.

Ross Millikan
  • 8,419
  • 30
  • 47
5

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.

Penny Hassett
  • 51
  • 2