IMO 2001 SL C2

Origin: CAN | Category: Combinatorics

Problem

Let n be an odd integer greater than 1 and let c1, c2, . . . , cn be integers. For each permutation a = (a1, a2, . . . , an) of {1, 2, . . ., n}, define S(a) = n i=1 ciai. Prove that there exist permutations a ̸= b of {1, 2, . . ., n} such that n! is a divisor of S(a) −S(b).

Solution

Suppose to the contrary that all the S(a)’s are different modulo n!. Then the sum of S(a)’s over all permutations a satisfies  a S(a) \equiv0+1+\cdot \cdot \cdot+ (n! −1) = (n!−1)n! \equivn! 2 (mod n!). On the other hand, the coefficient of ci in  a S(a) is equal to (n −1)!(1 + 2 + \cdot \cdot \cdot + n) = n+1 2 n! for all i, from which we obtain  a S(a) \equivn + 1 (c1 + \cdot \cdot \cdot + cn)n! \equiv0 (mod n!) for odd n. This is a contradiction.