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

4 answers to this question

  • 0

Alice is so kinky...

Spoiler

As ThunderCloud noted:

On 3/17/2018 at 4:31 PM, ThunderCloud said:

P(1) is the sum of the coefficients

So that is my first guess.  This lets me know a range that all a_i are in.  They can be from 0 to P(1) since all a_i are non-negative and their sum is P(1).

My second guess is the next higher power of 10 greater than P(1).  From this I can get every a_i since they will essentially all be listed in the response.

For example, lets say P(x) = 4 + 19*x + 23423433*x^2.  P(1) is 4+19+23423433=23423456.  The next higher power of 10 is 100000000.  P(100000000) = 4 + 19 * 100000000 + 23423433*100000000^2 = 234234330000001900000004.  You just need to split the response into groups of digits equal to the number of 0's in the power of 10 guessed, then read off the values.  e.g., (23423433)(00000019)(00000004)

So my number of guesses as a function of n is G(n) = 2.

The only thing this won't find is if Alice is keeping a few trailing 0's secret.  If a_n = 0, the polynomial is identical the polynomial of one lesser degree and no amount of guesses will find how many trailing coefficients are 0.

 

Share this post


Link to post
Share on other sites
  • 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.

×