13. A7 (RUS) For a polynomial $P$ of degree 2000 with distinct real coefficients let $M(P)$ be the set of all polynomials that can be produced from $P$ by permutation of its coefficients. A polynomial $P$ will be called $n$-independent if $P(n)=0$ and we can get from any $Q$ in $M(P)$ a polynomial $Q_{1}$ such that $Q_{1}(n)=0$ by interchanging at most one pair of coefficients of $Q$. Find all integers $n$ for which $n$-independent polynomials exist.
13. One can easily find $n$-independent polynomials for $n=0,1$. For example, $P_{0}(x)=2000 x^{2000}+\cdots+2 x^{2}+x+0$ is 0-independent (for $Q \in M\left(P_{0}\right)$ it suffices to exchange the coefficient 0 of $Q$ with the last term), and $P_{1}(x)=2000 x^{2000}+\cdots+2 x^{2}+x-(1+2+\cdots+2000)$ is 1-independent (since any $Q \in M\left(P_{1}\right)$ vanishes at $x=1$). Let us show that no $n$-independent polynomials exist for $n \notin\{0,1\}$. Consider separately the case $n=-1$. For any set $T$ we denote by $S(T)$ the sum of elements of $T$. Suppose that $P(x)=a_{2000} x^{2000}+\cdots+a_{1} x+a_{0}$ is $-1$-independent. Since $P(-1)=\left(a_{0}+a_{2}+\cdots+a_{2000}\right)-\left(a_{1}+a_{3}+\cdots+a_{1999}\right)$, this means that for any subset $E$ of the set $C=\left\{a_{0}, a_{1}, \ldots, a_{2000}\right\}$ having 1000 or 1001 elements there exist elements $e \in E$ and $f \in C \backslash E$ such that $S(E \cup\{f\} \backslash\{e\})=\frac{1}{2} S(C)$, or equivalently that $S(E)-\frac{1}{2} S(C)=e-f$. We may assume w.l.o.g. that $a_{0} > 0$. Furthermore, by the induction hypothesis the polynomials of the form $Q_{k}(x)$ take at least $2^{k-2}$ values at $x=n$. Hence the total number of values of $Q(n)$ for $Q \in M(P)$ is at least $1+1+2+2^{2}+\cdots+2^{m-1}=2^{m}$. Now we return to the main result. Suppose that $P(x)=a_{2000} x^{2000} +a_{1999} x^{1999}+\cdots+a_{0}$ is an $n$-independent polynomial. Since $P_{2}(x)=a_{2000} x^{2000} +a_{1998} x^{1998}+\cdots+a_{2} x^{2}+a_{0}$ is a polynomial in $t=x^{2}$ of degree 1000, by the lemma it takes at least $2^{1000}$ distinct values at $x=n$. Hence $\{Q(n) \mid Q \in M(P)\}$ contains at least $2^{1000}$ elements. On the other hand, interchanging the coefficients $b_{i}$ and $b_{j}$ in a polynomial $Q(x)=b_{2000} x^{2000}+\cdots+b_{0}$ modifies the value of $Q$ at $x=n$ by $\left(b_{i}-b_{j}\right)\left(n^{i}-n^{j}\right)=\left(a_{k}-a_{l}\right)\left(n^{i}-n^{j}\right)$ for some $k, l$. Hence there are fewer than $2001^{4}$ possible modifications of the value at $n$. Since $2001^{4}<2^{1000}$, we have arrived at a contradiction.