imo.wolfram.com
header_a.gif Wolfram Research  
mainscorescontestantscompetition problemsaboutphotoIMO Facts


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 k1, k2, ..., kn be given integers. For each of the n! permutations a = a1, a2, ..., an 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 = (a1, a2, ..., an). 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), k1 is multiplied by each i {1, ..., n} a total of (n - 1)! times, once for each permutation of {1, ..., n} in which a1 = i. Thus the coefficient of k1 in S(a) is

The same is true for all ki, 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.