Sonuva... I'm starting to think it would be easier to build a new robot. A polynomial function which is closed over the integers has to have rational coefficients, right? *tries to think of how to prove that* Because then you can just replace "integers n with |n| no greater than some number" with "rational numbers p/q with |p| and |q| no greater than some number."
I'll give you that any polynomial that sends integers to integers has to have rational coefficients. Spoiler: Proof For a degree n polynomial, you can determine it uniquely by evaluating it at n+1 points. So you evaluate it on 1, 2, ..., n+1. Since the inverse of a matrix with integer entries is a matrix with rational entries, you at least get that the coefficients are given by multiplying a matrix with integer entries (the values of the polynomial) by a matrix with rational entries.
Speaking of polynomials, here's a puzzle: Suppose I pick a polynomial P(x) whose coefficients are all nonnegative integers. You get to give me any algebraic number, i.e. any number that is the root of some polynomial with integer coefficients. So things like 3 or 4/5 or the square root of 2 or the golden ratio, but not things like e or pi, and I'll tell you the value of P of that algebraic number. How many times do you need me to evaluate P on a number before you can tell me with confidence all the coefficients of P?
The degree of P plus 1, isn't it? Unless the "all nonnegative integers" thing removes a degree of freedom, but I don't think it does.
I haven't told you the degree. And indeed, I won't do so. All you get is P evaluated on various numbers.
The degree of the polynomial plus two, then. With no negative coefficients, this function and its derivatives can't have any zeroes on R+, by Descartes' rule of signs. Therefore there can't be any local extrema, inflection points, etc. for positive values of x. I ask you for P(0), then P(1). If they're the same, P(x) = P(0). (A general polynomial might just happen to cross those two points, but by the mean value theorem that would require a local max or min between 0 and 1, which Descartes tells us cannot exist here.) If not, I find the equation of the line passing through (0, P(0)) and (1, P(1)). Then I ask you for P(2). If it's on that line, the line is P(x). (For a higher-degree polynomial to cross those three points would require an inflection point between 0 and 2, which I can prove by iterating the mean value theorem, and there's no such inflection point.) If not, I find the parabola passing through the three known points, ask you for P(3), and so on. As long as I keep plugging in different non-negative numbers, and the polynomial is of finite degree n, my prediction has to be right at guess n+2, which under these restrictions proves I have the right polynomial.
As soon as my prediction of the next point is right. I've ruled out the coincidence of a higher-degree polynomial hitting the same points.
Okay, I think I understand why your strategy works. So let's redo the problem: you specify the number of evaluations you get, then I pick a polynomial, and then you ask for the polynomial evaluated on various numbers. How many evaluations do you need?
... I have to pick a fixed number of evaluations before we start? That shouldn't be possible, whatever number I say you can just pick a polynomial with ten times that many terms.
So new puzzle, blatantly stolen from Steven Strogatz's twitter: Suppose you have a rectangular cake with a square top. The height of the cake is unknown. The top and sides of the cake all have icing. You want to divide the cake evenly into five portions so that each portion has the same amount of cake (by volume) and the same amount of icing. How? Let's say for now that the portions don't have to be single pieces, but the pieces of each portion must total 1/5 of the volume of the cake and 1/5 of the icing. Perhaps more precisely: divide a unit square into five portions so that each part has area 1/5 and contains 1/5 of the square's perimeter. For a slightly harder version, now suppose that each portion does have to be a single piece. There are a lot of solutions to this puzzle. Some of them generalize. Suppose instead of five pieces, you wanted to divide into 7 pieces, or 23 pieces, or n pieces for general n. How?
Spoiler: solution General solution for n pieces: Mark n points on the edge of the square, so as to divide its perimeter evenly into n equal pieces. Cut in a straight line from each of those points to the center of the square. Proof of equal area: First, consider those pieces whose chunk of the perimeter is on only one side of the square, so not including any corners of the square. These pieces must be triangles. They have a base that is 1/n the perimeter of the square - for a unit square, perimeter is 4, so the triangle's base is 4/n. The height of each triangle is the distance from the edge of a unit square to its center, so always 1/2. Area of a triangle is base times height times one half, so (4/n)(1/2)(1/2) = 1/n. Now consider pieces whose chunk of the perimeter does contain a corner. These pieces are quadrilaterals, but draw a diagonal (without cutting the cake) from the corner to the center of the square. This creates two triangles, with possibly different bases we will call a and b, but each of height 1/2. Their areas are a/4 and b/4 respectively, for a total area of (1/4)(a+b). But a+b is this piece's total chunk of the square's perimeter, so it must equal 1/n of that perimeter, that is 4/n. So the total area is (1/4)(4/n) = 1/n. For n<4 a single piece can contain more than one corner of the square, but the method of the previous paragraph extends to this case. Come to think of it, that's so general it ought to hold not just for a square cake, but any polygon where every side is equidistant from some interior point (that is, any polygon you could inscribe a circle in.)
