At the mathematics club, the teacher thought of a polynomial function of degree at most $n$. The students can ask for the function's value at any real number. How many function values need to be known in order to decide in all cases whether the function is even?
Solution. In the optimal case, students ask for the values of the function in pairs, that is, they ask for the value of the function for a positive $x$, and then for its negative counterpart. If the teacher thought of a polynomial function where only even exponents appear, the function is certainly even, and the students can ask for substitution values indefinitely, the function values of the pairs will always match.

If there is an odd exponent as well, the function is not even. Therefore, whether the function is even or not depends only on the odd exponent terms. For this reason, consider only the function $g(x)$ defined by the odd exponent terms.

A non-even polynomial function has the same value at a real $x$ and $-x$ only if the function and its reflection over the $y$-axis intersect at $x$. (The intersection point at $x=0$ does not count, since only positive-negative pairs are asked). If the students happen to ask for the function value at such an intersection point during their guessing, they will not realize that the function is actually not even; this takes 2 questions (for $x$ and $-x$).

If we consider the worst-case scenario, and the students find all such intersection points, they will need twice the number of positive intersection points plus two questions. If $a$ is such a positive point, then $g(-a)=g(a)$ holds, and since $g$ consists only of odd exponent terms, $g(-a)=-g(a)$; thus, $g(a)=0$. Therefore, $a$ is a root of $g$, and so is $g / x$, which consists only of even exponent terms. If the degree of $g$ is $k$, then there can be at most $(k-1) / 2$ such positive $a$ values, because the number of real roots of $g / x$ is at most its degree, $k-1$, and these roots are symmetrically placed around the $y$-axis.

This means at most $(k-1) / 2$ positive intersection points, but the students will also ask for their negatives, so they will ask $k-1$ questions. Then they will ask 2 more, and it will become clear that the function is not even. This amounts to $k-1+2=k+1$ questions.

Since $k$ represents the largest odd exponent, which is $n$ if $n$ is odd, and $n-1$ if $n$ is even; therefore, if $n$ is even, $n-1+1=n$ questions are sufficient, and if $n$ is odd, at least $n+1$ questions are needed.