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.
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
4
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$).
-
$\begingroup$ 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...$ $\endgroup$ Oct 9, 2015 at 6:12
-
$\begingroup$ $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 $\endgroup$– user99914Oct 9, 2015 at 6:16
-
$\begingroup$ Ok, Thanks I understand. Then how to find $(a_1-b_1)^2(a_2-b_2)^2\cdots (a_n-b_n)^2$? $\endgroup$ Oct 9, 2015 at 6:19
-
$\begingroup$ 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 $\endgroup$– user99914Oct 9, 2015 at 6:21
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
0
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.
