Let A1, A2, ..., An be any permutation of the numbers 1, 2, ..., n.

combinatorics/odd.permutation.product New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

Let A1, A2, ..., An be any permutation of the numbers 1, 2, ..., n.
Prove that, for n odd, the product (A1-1)(A2-2)...(An-n) is always an
even number.

[ Editor: the posting wrote the permutation as "A0,A1,A2,...,An" and
the product as "(A1-1)(A2-2)...(A3-3)". ]

-- Eric P Burke

Show solution

Use the pigeonhole principle.

Let n=2m+1 for simplicity.

Among the Ai there are m+1 odd numbers; however, there are only m even
number that can be subtracted from them, so some term is the difference
of two odd numbers.

-- Seth Breidbart <sethb@panix.com>