Rearrange the first $n$ integers $1, 2, 3, \ldots, n$, listing them as $a_1, a_2, \ldots a_n$. Prove that if $n$ is odd, then $(a_1 - 1)(a_2 - 2) \cdots (a_n - n)$ must be even, regardless of how the integers were initially rearranged.

We argue indirectly...

Assume $(a_1 - 1)(a_2 - 2) \cdots (a_n - n)$ is odd. Then each factor $(a_1 - 1)$, $(a_2 - 2)$, ... $(a_n - n)$ must be odd. This implies that $a_1, a_3, a_5, \cdots, a_n$ are all even, while $a_2, a_4, \cdots, a_{n-1}$ are all odd. Contemplating the potential use of the pigeon-hole principle (although we end up not using it after all), we count the number of odds and find there are $\displaystyle{\frac{(n-1)}{2}}$ of the $a_i$'s that are odd.

However, the numbers $a_1, a_2, \cdots a_n$ are precisely the numbers $1,2,3,\ldots,n$ -- just possibly in a different order. The number of odd numbers in this last list is $\displaystyle{\frac{(n-1)}{2} + 1}$, so we have a contradiction.

Hence, we must reject our initial assumption that the product $(a_1 - 1)(a_2 - 2) \cdots (a_n - n)$ could be odd. Instead, it must always be even.