Adaptive Queries

Jeremy Kun has an amusing and startling trick: pick any polynomial p(x)=c_{0}+c_{1}x+\cdots+c_{n}x^{n} where the c_{i} are non-negative integers and the degree, n, is any positive integer you like. Kun will then ask you one at a time for the value of p(x) at certain points. That is, he will ask for p(x_{1}), p(x_{2}), \ldots , p(x_{k}) for x_{i} of his choosing. What is the minimum number of points he will have to ask you about to discover the polynomial?

The answer will surprise and delight you. There isn't any heavy duty mathematics involved so everyone can enjoy the fun. Head on over and be surprised.

This entry was posted in General and tagged . Bookmark the permalink.