IMO 2000 SL A7

Origin: RUS | Category: Algebra

Problem

For a polynomial P of degree 2000 with distinct real co- eﬃcients let M(P) be the set of all polynomials that can be produced from P by permutation of its coeﬃcients. A polynomial P will be called n-independent if P(n) = 0 and we can get from any Q in M(P) a poly- nomial Q1 such that Q1(n) = 0 by interchanging at most one pair of coeﬃcients of Q. Find all integers n for which n-independent polynomials exist.

Solution

One can easily ﬁnd n-independent polynomials for n = 0, 1. For example, P0(x) = 2000x2000 + \cdot \cdot \cdot + 2x2 + x + 0 is 0-independent (for Q \inM(P0) it suﬃces to exchange the coeﬃcient 0 of Q with the last term), and P1(x) = 2000x2000+\cdot \cdot \cdot+2x2+x−(1+2+\cdot \cdot \cdot+2000) is 1-independent (since any Q \inM(P1) vanishes at x = 1). Let us show that no n-independent polynomials exist for n ̸\in{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) = a2000x2000+\cdot \cdot \cdot+a1x+a0 is −1- independent. Since P(−1) = (a0 +a2+\cdot \cdot \cdot+a2000)−(a1 +a3+\cdot \cdot \cdot+a1999), this means that for any subset E of the set C = {a0, a1, . . . , a2000} having 1000 or 1001 elements there exist elements e \inE and f \inC \ E such that S(E \cup{f} \ {e}) = 1 2S(C), or equivalently that S(E) −1 2S(C) = e −f. We may assume w.l.o.g. that a0 < a1 < \cdot \cdot \cdot < a2000. Suppose that E is a 1000-element subset of C containing b0, b1 but not b1999, b2000. By the −1-independence of P there exist e \inE and f \in C \ E such that S(E) −1 2S(C) = e −f. The same must hold for the set E′ = E \cup{b1999, b2000} \ {b0, b1}, so for some e′ \inE′ and f ′ \inC \ E′ we have S(E′) −1 2S(C) = e′ −f ′. It follows that b1999 + b2000 −b0 −b1 = S(E′) −S(E) = e + e′ −f −f ′. Therefore the transposition e \leftrightarrowf must involve at least one of the elements b0, b1, b1999, b2000.

There are 7994 possible transpositions involving one of these four ele- ments. On the other hand, by (SL93-12) the subsets E of C containing b0, b1 but not b1999, b2000 give at least 998\cdot999+1 distinct sums of elements, far exceeding 7994. This is a contradiction. For the case |n| \geq2 we need the following lemma. Lemma. Let n \geq2 be a natural number and P(x) = amxm+\cdot \cdot \cdot+a1x+a0 a polynomial with distinct coeﬃcients. Then the set {Q(n) | Q \inM(P)} contains at least 2m elements. Proof. We shall use induction on m. The statement is easily veriﬁed for m = 1. Assume w.l.o.g. that am < \cdot \cdot \cdot < a1 < a0. Consider two polynomials Qk and Qk+1 of the form Qk(x) = amxm + \cdot \cdot \cdot + akxk + a0xk−1 + bk−1xk−2 + \cdot \cdot \cdot + b1, Qk+1(x) = amxm + \cdot \cdot \cdot + ak+1xk+1 + a0xk + ckxk−1 + \cdot \cdot \cdot + c1, where (bk−1, . . . , b1) and (ck, . . . , c1) are permutations of the sets {ak−1, . . . , a1} and {ak, . . . , a1} respectively. We claim that Qk+1(n) \geq Qk(n). Indeed, since a0 −ck \leqa0 −ak and bj −cj < a0 −ak for 1 \leqj \leqn−1, we have Qk+1(n)−Qk(x) = (a0−ak)nk−(a0−ck)nk−1− (bk−1−ck−1)nk−2−\cdot \cdot \cdot−(b1−c1) \geq(a0−ak)(nk−nk−1−\cdot \cdot \cdot−n−1) > 0. Furthermore, by the induction hypothesis the polynomials of the form Qk(x) take at least 2k−2 values at x = n. Hence the total number of values of Q(n) for Q \inM(P) is at least 1+1+2+22+\cdot \cdot \cdot+2m−1 = 2m. Now we return to the main result. Suppose that P(x) = a2000x2000 +a1999x1999+a0 is an n-independent polynomial. Since P2(x) = a2000x2000 +a1998x1998+\cdot \cdot \cdot+a2x2+a0 is a polynomial in t = x2 of degree 1000, by the lemma it takes at least 21000 distinct values at x = n. Hence {Q(n) | Q \in M(P)} contains at least 21000 elements. On the other hand, interchang- ing the coeﬃcients bi and bj in a polynomial Q(x) = b2000x2000 + \cdot \cdot \cdot + b0 modiﬁes the value of Q at x = n by (bi −bj)(ni −nj) = (ak −al)(ni −nj) for some k, l. Hence there are fewer than 20014 possible modiﬁcations of the value at n. Since 20014 < 21000, we have arrived at a contradiction.