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.

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$).

• I know that a permutation can be written in two ways. In cycle form and in two line array form. But what is the meaning of $a_1,a_2,\cdots a_n$? How you get $(a_1-b_1) + (a_2 - b_2) +\cdots (a_n - b_n)$? How $(a_1+ \cdots +a_n)-(b_1+ \cdots +b_n) =(1+\cdots +n) -(1+\cdots + n)$? Did you take $a_1=1,a_2=2...$ Oct 9, 2015 at 6:12
• $a_1, \cdots, a_n$ is a permutation of $1, \cdots, n$ means just that $\{a_1, a_2, \cdots, a_n\} = \{1, 2, \cdots, n\}$. In particular $a_1 + \cdots + a_n = 1+\cdots + n$. @user1942348
– user99914
Oct 9, 2015 at 6:16
• Ok, Thanks I understand. Then how to find $(a_1-b_1)^2(a_2-b_2)^2\cdots (a_n-b_n)^2$? Oct 9, 2015 at 6:19
• You don't need to find the exact value. To show that this is even, it suffices to show that $a_i -b_i$ is even for some $i$ (Even number times any integers is still even) @user1942348
– user99914
Oct 9, 2015 at 6:21

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.

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.