IMO 1999 SL C7

Origin: IRE | Category: Combinatorics

Problem

Let p > 3 be a prime number. For each nonempty subset T of {0, 1, 2, 3, . . ., p−1} let E(T ) be the set of all (p−1)-tuples (x1, . . . , xp−1), where each xi \inT and x1 + 2x2 + \cdot \cdot \cdot + (p −1)xp−1 is divisible by p and let |E(T )| denote the number of elements in E(T ). Prove that |E({0, 1, 3})| \geq|E({0, 1, 2})|, with equality if and only if p = 5.

Solution

Denote A = {0, 1, 2} and B = {0, 1, 3}. Let fT (x) =  a\inT xa. Then define FT (x) = fT (x)fT (x2) \cdot \cdot \cdot fT (xp−1). We can write FT (x) = p(p−1) i=0 aixi, where ai is the number of ways to select an array {x1, . . . , xp−1} where xi \inT for all i and x1 + 2x2 + \cdot \cdot \cdot + (p −1)xp−1 = i. Let w = cos(2\pi/p) + i sin(2\pi/p), a pth root of unity. Noting that 1 + wj + w2j + \cdot \cdot \cdot + w(p−1)j = . p, p | j, 0, p ∤j, it follows that FT (1) + FT (w) + \cdot \cdot \cdot + FT (wp−1) = pE(T ). Since |A| = |B| = 3, it follows that FA(1) = FB(1) = 3p−1. We also have for p ∤i, j that FT (wi) = FT (w). Finally, we have FA(w) = p−1

i=1 (1 + wi + w2i) = p−1

i=1 1 −w3i 1 −wi = 1. Hence, combining these results, we obtain E(A) = 3p−1 + p −1 p and E(B) = 3p−1 + (p −1)FB(w) p . It remains to demonstrate that FB(w) \geq1 for all p and that equality holds only for p = 5. Since E(B) is an integer, it follows that FB(w) is an integer and FB(w) \equiv1 (mod p). Since fB(wp−i) = fB(wi), it follows that FB(w) = |fB(w)|2

fB(w2) 2 \cdot \cdot \cdot fB
w(p−1)/2

2 > 0. Hence FB(w) \geq1.

It remains to show that FB(w) = 1 if and only if p = 5. We have the formula (x−w)(x−w2) \cdot \cdot \cdot (x−wp−1) = xp−1 +xp−2 +\cdot \cdot \cdot+x+1 = xp−1 x−1 . Let fB(x) = x3 + x + 1 = (x −\lambda)(x −µ)(x −\nu), where \lambda, µ, and \nu are the three zeros of the polynomial fB(x). It follows that FB(w) = \lambdap −1 \lambda −1  µp −1 µ −1  \nup −1 \nu −1  = −1 3(\lambdap −1)(µp −1)(\nup −1), since (\lambda −1)(µ −1)(\nu −1) = −fB(1) = −3. We also have \lambda + µ + \nu = 0, \lambdaµ\nu = −1, \lambdaµ + \lambda\nu + µ\nu = 1, and \lambda2 + µ2 + \nu2 = (\lambda + µ + \nu)2 −2(\lambdaµ + \lambda\nu + µ\nu) = −2. By induction (using that (\lambdar + µr + \nur) + (\lambdar−2 + µr−2 + \nur−2)+(\lambdar−3+µr−3+\nur−3) = 0), it follows that \lambdar +µr +\nur is an integer for all r \inN. Let us assume FB(x) = 1. It follows that (\lambdap −1)(µp −1)(\nup −1) = −3. Hence \lambdap, µp, \nup are roots of the polynomial p(x) = x3−qx2+(1+q)x+1, where q = \lambdap + µp + \nup. Since fB(x) is an increasing function in real numbers, it follows that it has only one real root (w.l.o.g.) \lambda, the other two roots being complex conjugates. From fB(−1) < 0 < fB(−1/2) it follows that −1 < \lambda < −1/2. It also follows that \lambdap is the x coordinate of the intersection of functions y = x3 + x + 1 and y = q(x2 −x). Since \lambda < \lambdap < 0, it follows that q > 0; otherwise, q(x2 −x) intersects x3 +x+1 at a value smaller than \lambda. Additionally, as p increases, \lambdap approaches 0, and hence q must increase. For p = 5 we have 1+w+w3 = −w2(1+w2) and hence G(w) = $p−1 i=1 (1+ w2j) = 1. For a zero of fB(x) we have x5 = −x3 −x2 = −x2 + x + 1 and hence q = \lambda5 + µ5 + \nu5 = −(\lambda2 + µ2 + \nu2) + (\lambda + µ + \nu) + 3 = 5. For p > 5 we also have q \geq6. Assuming again FB(x) = 1 and defining p(x) as before, we have p(−1) < 0, p(0) > 0, p(2) < 0, and p(x) > 0 for a sufficiently large x > 2. It follows that p(x) must have three distinct real roots. However, since µp, \nup \inR ⇒\nup = µp = µp, it follows that p(x) has at most two real roots, which is a contradiction. Hence, it follows that FB(x) > 1 for p > 5 and thus E(A) \leqE(B), where equality holds only for p = 5.