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
. Since no two of them are congruent modulo
, we have that the set of all
for some
-tuple of
is a congruence class modulo
. 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.