Originally Posted by

**oldguynewstudent** Let n be odd and suppose $\displaystyle (x_{1},x_{2},\ldots,x_{n})$ is any permutation of [n]. Prove that the product $\displaystyle (x_{1}-1)(x_{2}-2)\cdots(x_{n}-n)$ is even. Is the result necessarily true if n is even? Give a proof or counterexample.

If the $\displaystyle x_{i}'s$ are written in ascending order, then each is paired with its additive inverse and each factor is zero, so the product is zero and we are done.

Since the product of any two even numbers is even and the product of an even number and an odd number is even, we need all the terms to be odd if the product is to be odd. Since n is odd, the first term $\displaystyle x_{1}$ and the last term $\displaystyle x_{n}$ will be odd. The sum (or difference) of any two numbers is even if they are both even or both odd and it is odd if one is even and one is odd. Starting with the $\displaystyle x_{i}'s$ in ascending order, we notice that each term has the two numbers paired so that each even $\displaystyle x_{i}$ is paired with an even number and each odd $\displaystyle x_{i}$ is paired with an odd number. We also notice that we can rearrange n-1 $\displaystyle x_{i}'s$ so that each even $\displaystyle x_{i}$ is paired with an odd number and each odd $\displaystyle x_{i}$ is paired with an even number. But by the pigeon hole principle, there is one $\displaystyle x_{i}$ left that is paired so that its term is even. Therefore with n being an odd number, the product of the terms must be even.

By a similar argument, if n is even, there is a way to rearrange the terms so that the product can be odd. Example: (2-1)(1-2)(4-3)(3-4).

Is this correct?