42nd International Mathematical OlympiadIMO 2001 Problems and SolutionsWashinton, DC, USAJuly 1-14, 2001 Problem 4Let n be an odd integer greater than 1, and let k_{1}, k_{2}, ..., k_{n} be given integers. For each of the n! permutations a = a_{1}, a_{2}, ..., a_{n} of 1, 2, ..., n, let
Prove that there are two permutations b and c, b c, such that n! is a divisor of S(b) - S(c). Solution Let S(a) be the sum of S(a) over all n! permutations a = (a_{1}, a_{2}, ..., a_{n}). We compute S(a) mod n! two ways, one of which depends on the desired conclusion being false, and reach a contradiction when n is odd. First way. In S(a), k_{1} is multiplied by each i {1, ..., n} a total of (n - 1)! times, once for each permutation of {1, ..., n} in which a_{1} = i. Thus the coefficient of k_{1} in S(a) is
The same is true for all k_{i}, so
Second way. If n! is not a divisor of S(a) - S(b) for any a b, then each S(a) must have a different remainder mod n!. Since there are n! permutations, these remainders must be precisely the numbers 0, 1, 2, ..., n! - 1. Thus
Combining (1) and (2), we get
Now, for n odd, the left side of (3) is congruent to 0 modulo n!, while for n > 1 the right side is not congruent to 0 (n! - 1 is odd). For n > 1 and odd, we have a contradiction. |