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?
Answer
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.)
No comments:
Post a Comment