Prove that $(a_1-b_1)^2(a_2-b_2)^2\cdots (a_n-b_n)^2$ is an even number. Let $a_1,a_2,\cdots ,a_n$ and $b_1,b_2,\cdots ,b_n$ be two permutations of $1,2,\cdots,n$ and $n$ is odd. Prove that 
$$(a_1-b_1)^2(a_2-b_2)^2\cdots (a_n-b_n)^2$$ 
is an even number.
I don't know where to start to solve this problem. Please help me. 
 A: For the product to be even we require one pair $(a_i, b_i)$ to have the same parity. Since $n$ is odd, there are $\frac{n-1}{2}$ even numbers and $\frac{n+1}{2}$ odd numbers in $\{1, 2, \dots, n\}$, so it is impossible to pair each even number with an odd number, so one pair must have the same parity and we are done.
A: Instead of $a_i$ and $b_i$, let us write $a(i)$ and $b(i)$ for more clarity. Because multiplication is commutative, for any permutation $\sigma\in S_n$ we have
$$(a(1)-b(1))^2\cdots (a(n)-b(n))^2=\prod_{i=1}^n(a(i)- b(i))^2 =\prod_{i=1}^n(a(\sigma(i)) - b(\sigma(i)))^2 \tag{1}$$

(This is just a fancy way of expressing commutativity. For example, if $n=3$, we have $$(a(1)-b(1))^2(a(2)-b(2))^2(a(3)-b(3))^2 = (a(3)-b(3))^2(a(1)-b(1))^2(a(2)-b(2))^2 = (a(\sigma(1)) - b(\sigma(1))^2(a(\sigma(2)) - b(\sigma(2))^2(a(\sigma(3)) - b(\sigma(3)))^2$$ for permutation $\sigma(1) = 3$, $\sigma(2) = 1$, $\sigma(3) = 2$.)

Now, if we let $\sigma = a^{-1}$ be the inverse of permutation $a$, from $(1)$ we get
$$(a(1)-b(1))^2\cdots (a(n)-b(n))^2 = \prod_{i=1}^n(a(a^{-1}(i)) - b(a^{-1}(i)))^2 = \prod_{i=1}^n(i - b(a^{-1}(i)))^2$$
so let us denote $c = b\circ a^{-1}$. 
In order for $(1-c_1)^2\cdots(n-c_n)^2$ to be odd, $c_i$ must be of opposite parity of $i$, but, $n$ is odd so $\{1,2\ldots,n\}$ has exactly $\frac{n-1}2$ even and $\frac{n+1}2$ odd numbers, so by pigeonhole principle there is at least one pair $(i,c_i)$ such that both $i$ and $c_i$ are odd, and thus $i-c_i$ is even.
A: Note that it suffices to show that $a_i - b_i$ is even for some $i$. Using 
$$\begin{split} (a_1-b_1) + (a_2 - b_2) +\cdots (a_n - b_n) &= (a_1+ \cdots +a_n)-(b_1+ \cdots +b_n) \\
&=(1+\cdots +n) -(1+\cdots + n)\\
&= 0.
\end{split}$$
As $n$ is odd, one of them $a_i - b_i$ must be even (as adding $n$ odd terms will give you an odd number, not $0$). 
