IMO 1995 SL N6

Origin: POL | Category: Number Theory

Problem

Let p be an odd prime. Find the number of p-element subsets A of {1, 2, . . ., 2p} such that the sum of all elements of A is divisible by p.

Solution

We shall consider the set M = {0, 1, . . ., 2p −1} instead. Let M1 = {0, 1, . . ., p −1} and M2 = {p, p + 1, . . . , 2p −1}. We shall denote by |A| and \sigma(A) the number of elements and the sum of elements of the set A; also, let Cp be the family of all p-element subsets of M. Define the mapping T : Cp \toCp as T (A) = {x + 1 | x \inA \capM1} \cup{A \capM2}, the addition being modulo p. There are exactly two fixed points of T : these are M1 and M2. Now if A is any subset from Cp distinct from M1, M2, and k = |A \capM1| with 1 \leqk \leqp −1, then for i = 0, 1, . . . , p −1, \sigma(T i(A)) = \sigma(A) + ik (mod p). Hence subsets A, T (A), . . . , T p−1(A) are distinct, and exactly one of them has sum of elements divisible by p. Since \sigma(M1), \sigma(M2) are divisible by p and Cp \ {M1, M2} decomposes into fam- ilies of the form {A, T (A), . . . , T p−1(A)}, we conclude that the required number is 1 p(|Cp| −2) + 2 = 1 p 
2p p  −2

Second solution. Let Ck be the family of all k-element subsets of {1, 2, . . ., 2p}. Denote by Mk (k = 1, 2, . . . , p) the family of p-element mul- tisets with k distinct elements from {1, 2, . . ., 2p}, exactly one of which ap- pears more than once, that have sum of elements divisible by p. It is clear that every subset from Ck, k < p, can be complemented to a multiset from Mk \cupMk+1 in exactly two ways, since the equation (p −k)a \equiv0 (mod p) has exactly two solutions in {1, 2, . . ., 2p}. On the other hand, every mul- tiset from Mk can be obtained by completing exactly one subset from Ck. Additionally, a multiset from Mk can be obtained from exactly one subset from Ck−1 if k < p, and from exactly p subsets from Ck−1 if k = p. Therefore |Mk| + |Mk+1| = 2|Ck| = 2
2p k  for k = 1, 2, . . ., p −2, and |Mp−1| + p|Mp| = 2|Cp−1| = 2
2p p−1  . Since M1 = 2p, it is not difficult to show using recursion that |Mp| = 1 p 
2p p  −2

Third solution. Let \omega = cos 2\pi p + i sin 2\pi p . We have $2p i=1(x −\omegai) = (xp −1)2 = x2p −2xp + 1; hence comparing the coefficients at xp, we obtain  \omegai1+\cdot\cdot\cdot+ip = p−1 i=0 ai\omegai = 2, where the first sum runs over all p-subsets {i1, . . . , ip} of {1, . . . , 2p}, and ai is the number of such subsets for which i1 + \cdot \cdot \cdot + ip \equivi (mod p). Setting q(x) = −2 + p−1 i=0 aixi, we obtain q(\omegaj) = 0 for j = 1, 2, . . ., p−1. Hence 1+x+\cdot \cdot \cdot+xp−1 | q(x), and since deg q = p−1, we have q(x) = −2+p−1 i=0 aixi = c(1+x+\cdot \cdot \cdot+xp−1) for some constant c. Thus a0 −2 = a1 = \cdot \cdot \cdot = ap−1, which together with a0 + \cdot \cdot \cdot + ap−1 =
2p p  yields a0 = 1 p 
2p p  −2