Alice is allowed to choose an arbitrary polynomial p(x) of any degree with nonnegative integer coefficients. Bob can infer the coefficients of p(x) by only two evaluations as follows. He chooses a real number a and Alice communicates p(a) to him. He then chooses a real number b and Alice communicates p(b) to him. What values of a and b helped Bob succeed and how?

In Dec 2010, Aravind Srinivasan pointed me to R J Lipton's blog article (see "Gift III" in the article). The puzzle originally appeared as "A Perplexing Polynomial Puzzle" by I. B. Keene in The College Mathematical Journal, Volume 36, No. 2, pp. 100, March 2005.

It is quite intriguing that merely two evaluations of the polynomial suffice! Here is the trick: the coefficients of p(x) are exactly the coefficients used to represent the integer p(p(1) + 1) in base p(1) + 1. So Bob first asks for p(1), then ask for p(p(1) + 1) and writes p(p(1) + 1) in base p(1) + 1 to infer all coefficients of p(x).

For the second evaluation, any integer greater than p(1) + 1 would also suffice. For example, if p(1) were 6, then Bob could have chosen 10 for the second evaluation and read off coefficients of p(x) from the decimal representation of p(10).

References: Detailed explanation of the solution. On a Perplexing Polynomial Puzzle by Bettina Richmond in The College Mathematics Journal, Volume 41, Number 5, November 2010, pp. 400-403(4).