짝치환과 홀치환의 성질 증명 (ft. 15퍼즐)

짝치환(even permutation)이란, 짝수 개의 호환의 곱으로 나타나는 치환이고, 홀치환(odd permutation)이란, 홀수 개의 호환의 곱으로 나타나는 치환이다. 이렇게 짝치환과 홀치환이 well-defined 되기 위해서는, 어떤 치환이 짝치환이면서 홀치환일 수 없다는 증명이 필요하다.

일반적인 증명 방법과 다르게, 샘 로이드의 15퍼즐에서 아이디어를 얻은 조금 다른 증명을 소개한다.

 

샘로이드의 15퍼즐 - 풀 수 없는 예

 

증명

어떤 치환 $\sigma$를 다음과 같은 1행 표기법으로 표현하자.

$$\sigma = \left( \sigma(1)\quad  \sigma(2)\quad \cdots\quad  \sigma(n) \right)$$

이러한 치환 $\sigma$를 단순히 일종의 수열이라고 생각할 때,

$$f(k) := k\text{보다 뒤에 있으면서 $k$보다 작은 수의 개수}$$라고 정의하고, $$F:=\sum_{k=1}^{n} f(k)$$로서 치환 $\sigma$에 대응하는 수 $F$를 정의하자.

 

예를 들어, $n=5$에서 항등치환 $ (1\; 2\; 3\; 4\; 5) $은 오름차순으로 정렬되어 있으므로 $F=0$이다.

반면 치환 $ (1\; 2\; 5\; 4\; 3) $에서 $F=3$이다. 5 뒤에 5보다 작은 수가 2개 존재하고, 4 뒤에 4보다 작은 수가 1개 존재하기 때문이다.

 

치환 $\sigma$에서 임의의 호환 $(i, \ j)$를 시행하였을 때, 새로운 치환 $\sigma'$이 되며 이에 대응하는 $F'$이 생긴다.

이때 $F$와 $F'$의 기우성(홀짝성)이 다르다는 것을 증명하면 충분하다.

왜냐하면 $F$는 항등치환일 때 0이고, 임의의 호환을 시행하였을 때 기우성이 바뀌므로, $F$가 짝수면 짝치환, $F$가 홀수면 홀치환이 되기 때문이다.

 

치환 $\sigma$를 나타내는 수열에서 다음과 같이 몇 가지 기호를 약속하자.

$$\sigma = \left( \cdots, \; i,\; \underbrace{\cdots}_{\text{A}}, \; j, \; \underbrace{\cdots}_{\text{B}} \right) $$

$$ a_i := \text{A에서 $i$보다 작은 수의 개수} $$

$$ b_i := \text{B에서 $i$보다 작은 수의 개수} $$

$$ a_j := \text{A에서 $j$보다 작은 수의 개수} $$

$$ b_j := \text{B에서 $j$보다 작은 수의 개수} $$

 

이제 호환 $(i, \ j)$를 시행하였을 때, $F'-F$를 생각해보자.

$f(i)$와 $f(j)$는 당연히 바뀌고, 또 A 영역에 있는 수들도 값이 바뀐다.

 

case 1) $ i<j $

$f(i) = a_i + b_i $,   $f(j) = b_j $

$f'(i)=b_i$,   $f'(j)=a_j+b_j+1$,   A영역에서 추가되는 값 $a_j-a_i$

따라서 $F'-F=2a_j-2a_i+1$ 이므로, $F$와 $F'$은 기우성이 다르다.

 

case 2) $ i>j $

$f(i) = a_i + b_i +1 $,   $f(j) = b_j $

$f'(i)=b_i$,   $f'(j)=a_j+b_j$,   A영역에서 추가되는 값 $a_j-a_i$

따라서 위 경우와 마찬가지로 $F'-F=2a_j-2a_i+1$ 이므로, $F$와 $F'$은 기우성이 다르다.

 

증명 완료.

 

 

 

P.S.

2년 전에 생각했던 증명을 귀차니즘 이슈로 이제야 포스팅...