13th Eötvös 1906 Problem 3 (a 1 , a 2 , ... , a n ) is a permutation of (1, 2, ... , n). Show that ∏ (a i - i) is even if n is odd.
Problem 854
Official 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 [email protected] 29 Oct 2003 Last corrected/updated 29 Oct 03