, 2021

There doesn't exist such a $n$.
Let $x_1 < x_2 < \cdots < x_{2n}$ be real numbers chosen by the magician. We will construct two distinct polynomials $P(x)$ and $Q(x)$, each of degree $n$, such that the member of audience will write down the same sequence for both polynomials. This will mean that the magician cannot distinguish $P$ from $Q$.

Claim. There exists a polynomial $P(x)$ of degree $n$ such that $P(x_{2i-1}) + P(x_{2i}) = 0$ for $i = 1, 2, \dots, n$.

Proof. We want to find a polynomial $a_n x^n + \cdots + a_1 x + a_0$ satisfying the following system of equations:
$$\left\{ \begin{array}{l} (x_1^n + x_2^n)a_n + (x_1^{n-1} + x_2^{n-1})a_{n-1} + \cdots + 2a_0 = 0 \\ (x_3^n + x_4^n)a_n + (x_3^{n-1} + x_4^{n-1})a_{n-1} + \cdots + 2a_0 = 0 \\ \cdots \\ (x_{2n-1}^n + x_{2n}^n)a_n + (x_{2n-1}^{n-1} + x_{2n}^{n-1})a_{n-1} + \cdots + 2a_0 = 0 \end{array} \right.$$
We use the well known fact that a homogeneous system of $n$ linear equations in $n+1$ variables has a nonzero solution. (This fact can be proved using induction on $n$, via elimination of variables.) Applying this fact to the above system, we find a nonzero polynomial $P(x)$ of degree not exceeding $n$ such that its coefficients $a_0, \dots, a_n$ satisfy this system. Therefore $P(x_{2i-1}) + P(x_{2i}) = 0$ for all $i = 1, 2, \dots, n$. Notice that $P$ has a root on each segment $[x_{2i-1}, x_{2i}]$ by the Intermediate Value theorem, so $n$ roots in total. Since $P$ is nonzero, we get $\deg P = n$.

Now consider a polynomial $P(x)$ provided by the Claim, and take $Q(x) = -P(x)$. The properties of $P(x)$ yield that $P(x_{2i-1}) = Q(x_{2i})$ and $Q(x_{2i-1}) = P(x_{2i})$ for all $i = 1, 2, \dots, n$. It is also clear that $P \neq -P = Q$ and $\deg Q = \deg P = n$.