February 16–February 22, 2010

Problem

Cynthia is thinking of a polynomial P(x). She tells you that all of the coefficients are non-negative integers, and if you query her about any integer value x, she will the tell you the value of P(x). However, she won't tell you anything else about the polynomial—you don't even know the degree.

She brags that she has a "really hard" polynomial that you won't be able to figure out, even after many queries. How can you surprise her?

Solution

here

List of solvers

The following people succeeded in "surprising" Cynthia: Daniel Nollette, Enkhbileg Ganbat, Eric Bensley (undergrad); Jacob Lewis (graduate); Steve Wilmarth, Mike Goodman (outside).

Other people found the polynomial, but it took them lots of queries: Peiyush Jain, Lloyd Sakazaki, T.R. Mukundan, Chaitanya Rachabattuni, Brett Kleinschmidt.

Enkhbileg Ganbat wins the prize!