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