Perplexing Polynomial


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

Previous Puzzle: Loop in a Linked List

Given the head of a linked list, find if it contains a loop or not, in linear time. Can you accomplish it with only O(1) extra space? Can you do it without modifying the list in any way?

An enemy spy has poisoned one out of 1000 barrels of wine in a king's cellar. Even a sip of the poisoned wine has potency to kill. However, the effects of the poison show only in 30 days. The king asks the royal jailor to identify the poisoned barrel within 30 days. What is the least number of prisoners the jailor must employ to identify the poisoned barrel?

23 Dec 2010
© Copyright 2008—2017, Gurmeet Manku.