Writeup: IMO Shortlist 2001 C2

20 Apr, 2025

Problem Statement

Let $n$ be an odd integer greater than 1 and let $c_{1}, c_{2}, \dots, c_{n}$ be integers. For each permutation $a = (a_{1}, a_{2}, \dots, a_{n})$ of ${1, 2, \dots, n}$ , define $S (a) = \sum_{i = 1}^{n} c_{i} a_{i}$ . Prove that there exist permutations $a \neq b$ of ${1, 2, \dots, n}$ such that $n!$ is a divisor of $S (a) - S (b)$ .

My Solution

Assume not for the sake of contradiction. Then note that $S (a)$ must take on $n!$ different remainders mod $n!$ , one for each of the permutations of ${1, 2, \lodts, n}$ , otherwise there will be distinct permutations $a$ and $b$ such that $S (a)$ and $S (b)$ have the same remainder mod $n!$ and therefore $n! | S (a) - S (b)$ .

Then we should have the remainders be $0, 1, 2, \dots, n! - 1$ , and

\sum S (a) \equiv 0 + 1 + \dots + n! \equiv \frac{(n! - 1) (n!)}{2} mod n! .

Since $n$ is odd, $\sum S (A)$ should not be divisible by $n!$ because we don't have enough powers of $2$ .

But we should also have

\sum S (a) \equiv \sum c_{i} (1 + 2 + \dots + n) (n - 1)! \equiv \sum c_{i} \frac{(n) (n + 1)}{2} (n - 1)! \equiv \frac{(n + 1)!}{2} \sum c_{i} .

Since $n$ is odd, $n + 1$ is even so $\frac{(n + 1)!}{2}$ must be divisible by $n!$ since $\frac{n + 1}{2}$ is an integer. So $\sum S (A)$ should be divisible by $n!$ .

We have a contradiction. So there must exist permutations $a \neq b$ of ${1, 2, \dots, n}$ such that $n!$ is a divisor of $S (a) - S (b)$ .