Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
    
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. – caonayemi Jan 29 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 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 at 22:44
    
Thanks, @MichaelSeifert; I missed that limitation on n when I read the question. – caonayemi Jan 30 at 1:22
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 1 at 18:51
up vote 81 down vote accepted
+200

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

share|improve this answer
4  
I didn't understand what you meant by "read off" the coefficients, but then I tried it with a couple of polynomials. Good work! – caonayemi Jan 29 at 17:34
3  
@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 at 18:22
4  
@Matt: Slight modification: Chunk in groups of $n$ digits starting from the right. – Deusovi Jan 29 at 18:56
7  
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 at 22:59
4  
@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 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.

share|improve this answer
    
+1 Lovely practical solution to the problem ;c) – BmyGuest Feb 22 at 14:25

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.

share|improve this answer
4  
…but then P(x) doesn't have positive integer coefficients. – Jared Jan 31 at 13:24
    
Whoops, my bad. I don't know if my objection is salvageable – Penny Hassett Jan 31 at 16:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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