42nd International Mathematical Olympiad

IMO 2001 Problems and Solutions

Washinton, DC, USA
July 1-14, 2001

Problem 4

Let n be an odd integer greater than 1, and let k₁, k₂, ..., k_n be given integers. For each of the n! permutations a = a₁, a₂, ..., 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₁, a₂, ..., 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₁ is multiplied by each i {1, ..., n} a total of (n - 1)! times, once for each permutation of {1, ..., n} in which a₁ = i. Thus the coefficient of k₁ 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.