Jump to content
BrainDen.com - Brain Teasers
  • 0
BMAD

Help Bob find Alice's P(x)$%^

Question

Alice and Bob are playing the following game: Alice has a secret polynomial P(x) = a_0 + a_1 x + a_2 x^2 + … + a_n x^n, with non-negative integer coefficients a_0, a_1, …, a_n. At each turn, Bob picks an integer k and Alice tells Bob the value of P(k). Find, as a function of the degree n, the minimum number of turns Bob needs to completely determine Alice’s polynomial P(x).

Share this post


Link to post
Share on other sites

3 answers to this question

  • 0

Hmmm… assuming n is known to Bob, my first thoughts…

Spoiler

Naively, as there are n+1 unknown terms to be found, there would not need to be more than n+1 distinct choices of k to yield a solvable set of linear equations. In particular, P(0) = a_0, P(1) is the sum of the coefficients, P(-1) gives the sum of the even-indexed coefficients minus the sum of the odd-indexed coefficients, etc.

I haven't thought of a way to leverage the fact that each coefficient is an integer ≥ 0 to further reduce the number of P(k)'s Bob would need to fewer than n+1, but there could be one…

 

Share this post


Link to post
Share on other sites
  • 0
14 hours ago, BMAD said:

n is not known

Well, in that case…

Spoiler

Bob can determine a0 by asking for P(0). After that, Bob can check for additional terms by guessing another positive integer, say, 1; if P(1) is different than P(0), Bob solves for a1 assuming it is the only remaining term. Bob then tests a new value, maybe P(2)… if it is different than what would be predicted by the polynomial thus far, Bob then re-solves for a1 and a2 assuming there are no further remaining terms. Then tests another value… etc. Bob stops when testing confirms his assumption that there are no further terms — because each of the nonzero coefficients is positive, a single unique positive test value could determine whether any additional nonzero terms existed or not.

 

So, all in all, I think that Bob would need n +  2 test values to determine for certain the coefficients of Alice's n-degree polynomial.

 

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.

×