The answer is No. We will show the following lemma, which basically solves the problem. Lemma. Given $x_1,x_2,...,x_{2n}$ there exists a nonzero polynomial $P$ with degree at most $n$ such that $$P(x_1)+P(x_2)=P(x_3)+P(x_4)=...=P(x_{2n-1})+P(x_{2n})=0$$Proof. It suffices to show that there exists real numbers $a_n,...,a_0$ such that $$\sum_{k=1}^na_k(x_{2i-1}^n+x_{2i}^n)=0$$for all $1\leq i\leq n$. Let $v_i$ be the vector $$(x_{2i-1}^n+x_{2i}^n,x_{2i-1}^{n-1}+x_{2i}^{n-1},...,x_{2i-1}+x_{2i},2)$$Let $U$ be the vector space spanned by $v_1,...,v_n$. By a well-known fact, $$\dim U^{\perp}=\dim\mathbb R^{n+1}-\dim U\geq 1$$so there exists some nonzero $u=(u_n,...,u_0)$ in $U^{\perp}$ It suffices to take $(a_n,...,a_0)=(u_n,...,u_0)$, then by definition, $$\sum_{k=1}^na_k(x_{2i-1}^n+x_{2i}^n)=u\cdot v_i=0$$as desired.$\blacksquare$ Now the audience can just chooses this $P$, then the magician cannot distinguish between $P$ and $-P$, so we are done.

Can anyone tell me the flaw in this method? Suppose the magician announces $n=2$ and the numbers as $1,2,3,5$. It should be noted that $3P(1)-8P(2)+6P(3)=P(5)$ holds for any quadratic $P$ So the magician on seeing the numbers on the board can put different permutations in the equation $3x-8y+6z=w$ and see which tuple satisfy them. Once some tuple $(x,y,z,w)$ fits the expression he would let $$x=P(1)=a+b+c$$$$y=P(2)=4a+2b+c$$and $$z=P(3)=9a+3b+c$$and solve for a,b,c and report the quadratic as $$P(x)=ax^2+bx+c$$.By this method he would always be able to report right? If anyone finds a flaw please give a counterexample.

This message is regarding this post.

Does anyone know how to prove the following comment from the official solution?

@above bump

This problem is magic No. Let $V$ be the vector space of polynomials with degree at most $n$. Then, consider the linear map from $V$ to $\mathbb{R}^n$ that maps $P$ to $\left(P(x_1)+P(x_2),P(x_3)+P(x_4),\ldots,P(x_{2n-1})+P(x_{2n})\right)$. The image has dimension at most $n$ and $V$ has degree $n+1$, hence the kernel is nontrivial. We can then choose any $P$ from the kernel and it would be indistinguishable from $-P$.

We claim, that the answer is no. It's suffice to construct polynomials $P\neq Q$ of degree $n,$ for which will be written the same sequence of values. Claim. We may choose such $P,$ that $P(x_{2k-1})+P(x_{2k})=0$ for every $1\leq k\leq n.$ Proof. All equations $\sum_{t=0}^n (x_{2k-1}^t+x_{2k}^t)a_t$ $=0$ form a system of $n$ linear equations with $n+1$ variables $a_0,a_1,...,a_n,$ which has nontrivial solution. This defines polynomial $P(x)$ with root on each segment $[x_{2k-1};x_{2k}],$ so in particular $\deg P=n$ $\Box$ Now it's clearly enough to put $Q=-P.$

Consider the following $n$ equations in the $n+1$ variables $a_0,\ldots,a_n$: \begin{align*} (x_1^n+x_2^n)a_n+\cdots+(x_1+x_2)a_1+2a_0&=0\\ (x_3^n+x_4^n)a_n+\cdots+(x_3+x_4)a_1+2a_0&=0\\ &\vdots\\ (x_{2n-1}^n+x_{2n}^n)a_n+\cdots+(x_{2n-1}+x_{2n})a_1+2a_0&=0. \end{align*}Since this system has at least one solution, namely the trivial $(a_0,\ldots,a_n)=(0,\ldots,0)$, it must have at least two solutions (actually infinitely many), i.e. at least one nontrivial one where some variable is nonzero. Take such a solution and construct the polynomial $P(x)=a_nx^n+\cdots+a_1x+a_0$, which obeys the equations $P(x_1)+P(x_2)=0,\ldots,P(x_{2n-1})+P(x_{2n})=0$. Therefore there $P$ must have a root in $[x_1,x_2],\ldots,[x_{2n-1},x_{2n}]$ by the intermediate value theorem, so $P$ has at least $n$ roots and is thus degree $n$. But then, if the audience member answers $P$, the multiset of values will be the same as that of $-P$, so the magician is doomed to fail. $\blacksquare$

Solved with yofro. Consider the map from polynomials of ${\mathbb R}^{n+1} \to {\mathbb R}^{2n}$ under evaluation at $x_1, \dots, x_{2n}$. Note that by the fundamental theorem of algebra this is injective. Let $I$ be its image. Consider the vector space $K$ consisting of $(a_1, a_2, \dots, a_{2n})$ such that $a_i = -a_{n+i}$. Since $\dim K = n$ and $\dim I = n + 1$, it follows that $K \cap I \ne \{0\}$ as $n \ge \dim(K + I) = \dim K + \dim I - \dim K \cap I$. Thus, let $p$ be a nonzero vector in $K \cap I$. It has a unique pre-image $P$ under the map. However, then $-P$ maps to a permutation of $P$ under the map, and thus the magician can't uniquely determine $P$ from the unordered evaluation.

Let $V$ be the vector space of polynomials on real coefficients with degree at most $n$. Consider the linear transformation $T \colon V \to \mathbb{R}^n$ mapping \[ p \mapsto (p(x_1)+p(x_2), p(x_3) + p(x_4), \ldots, p(x_{2n-1}) + p(x_{2n})).\]Since $\dim V > \dim \mathbb{R}^n$ this map must have a kernel of dimension at least $1$. Given any non-zero $q \in \ker T$ we must have $q(x_{2k}) = -q(x_{2k+1})$. Thus, \[ \{ q(x_i) \colon 1 \leq i \leq 2n \} = \{ -q(x_i) \colon 1 \leq i \leq 2n \} \]Thus, we have found two polynomials with the same multiset of values making the magician's trick impossible.