2001 IMO Shortlist Problems/C2
Problem
Let be an odd integer greater than 1 and let be integers. For each permutation of , define . Prove that there exist permutations of such that is a divisor of .
Solution
We shall prove this by contradiction. Assume that for some -tuple of there does not exist two permutations and of such that . Note that there are distinct permutations of , which means there are distinct sums . Because no two of them are congruent modulo , we have that for some -tuple of there exists a unique permutation of such that for all integers . This means that the sum of every is congruent to . However, that same sum is congruent to
Note that , so , so divides the sum. However, the sum is also congruent to modulo , and is odd, so couldn't possibly divide the sum. This leads to a contradiction, so our previous assumption must be false. This proves the problem statement.