Answer to polynomial puzzle.

==ANSWER==

Ask me for k = P(1). As all the coefficients are non-negative, and P(1) is the sum of them, they must all be less than or equal to k - in other words, our coefficients a_i have 0 <= a_i <= P(1).

Choose n > P(1). Ask me for P(n) - this could be, for instance, P(P(1) + 1). This is an integer, and so it has a representation in base n - and a moment's thought shows us that its digits base n are exactly the coefficients of the polynomial.

An interesting choice of n (less minimal but perhaps more illustrative) is 10^d, where d is the number of digits in k = P(1). Why? Well, then, you can read off the solution directly from P(n). Here's an example: say P(x) = 456x^2  + 1888x + 19394. Then P(1) = 21738, so d = 5. What's P(10^5)? It's 4560188819394 - or, in blocks of 5, 00456, 01888, 19394.

The key observation from someone else for me was that P(1) necessarily tells you something about how big an n is needed to let the leading term of the polynomial dominate in P(n), which certainly lets you find the order and leading coefficient. As I realised and as the above shows, however, it's actually enough to give you everything.