A polynomial p(x) of degree 2000 with distinct real coefficients satisfies condition n if (1) p(n) = 0 and (2) if q(x) is obtained from p(x) by permuting its coefficients, then either q(n) = 0, or we can obtain a polynomial r(x) by transposing two coefficients of q(x) such that r(n) = 0. Find all integers n for which there is a polynomial satisfying condition n.
Solution
Answer: n = 0 and 1.
If p(x) has zero coefficient of x0 then it obviously satisfies condition 0. Similarly if p(x) = a2000x2000 + ... + a0 and we put a0 = a1 + ... + a2000, then it satisfies condition 1. [In both cases all we need to do to get q(n) = 0 is to get the right coefficient of x0.]
It remains to show that if n is not 0 or 1, then p(x) cannot satisfy condition n. We consider first the case |n| > 1. The idea is that we can get too many different values at x = n by permuting the coefficients of p(x) for condition n to hold. Specifically, we claim that we can get at least 22000 different values. Now suppose q(x) = b2000x2000 + ... + b0 is obtained by permuting the coefficients of p(x). Then if we transpose the coefficients bi and bj, then we increase the value at x = n by (binj + bjni - bini - bjnj) = d. Now as q(x) ranges over all possibilities and i and j range over all possibilities, d has less than 20014 possible values, because there are 2001 choices for i, 2000 choices for j, then 2001 choices for the coefficient of p(x) which equals bi and 2000 choices for the coefficient of p(x) which equals bj. So if q(n) = 0, then r(n) has less than 20014 possible values (where r(x) is obtained from q(x) by transposing two coefficients). But if p(x) satisfies condition n, then r(x) could be any polynomial obtained by permuting the coefficients of p(x). Contradiction, since 20014 < 22000.
© John Scholes
jscholes@kalva.demon.co.uk
10 Oct 2002