Let n1, n2, ... , nm be integers, where m is odd. Let x = (x1, ... , xm) denote a permutation of the integers 1, 2, ... , m. Let f(x) = x1n1 + x2n2 + ... + xmnm. Show that for some distinct permutations a, b the difference f(a) - f(b) is a multiple of m!.
Solution
This is a simple application of the pigeon hole principle.
The sum of all m! distinct residues mod m! is not divisible by m! because m! is even (since m > 1). [The residues come in pairs a and m! - a, except for m!/2.].
However, the sum of all f(x) as x ranges over all m! permutations is 1/2 (m+1)! ∑ ni, which is divisible by m! (since m+1 is even). So at least one residue must occur more than once among the f(x).
© John Scholes
jscholes@kalva.demon.co.uk
12 Aug 2001
Last corrected/updated 12 Aug 2001