13th Eötvös 1906

(a₁, a₂, ... , a_n) is a permutation of (1, 2, ... , n). Show that ∏ (a_i - i) is even if n is odd.

Solution

Put n = 2m+1. Suppose there are k values of i for which both a_i and i are odd. Then since there are m+1 odd values in total, there must be m+1-k values for which a_i is odd, but i is not and m+1-k values for which a_i is even and i is odd. The remaining k-1 values have both a_i and i even. Since a_i - i is odd iff a_i and i have opposite parity, there are 2(m+1-k) values for which that is true. Since that is even, there must be at least one value for which a_i and i have the same parity. Hence the product is even.

13th Eötvös 1906

© John Scholes
jscholes@kalva.demon.co.uk
29 Oct 2003
Last corrected/updated 29 Oct 03