Invariant 불변식

수업에서는 위치 바꾸는 퍼즐문제를 통해 설명한다.

불변식이란?

초기 상태에서 목표 상태로 이행할 수 없음을 증명할때 가장 효과적으로 동원되는 방법이 불변식을 찾아서 목표 상태에 그 불변식이 존재하지 않음을 증명하는 방법이다. 초기 상태에 가할 수 있는 여러 변화들이 있을 떄 (수업에서 나온 예시는 퍼즐의 행 이동과 열 이동) 이 변화들의 조합으로는 절대 바뀌지 않는 성질이 불변식이다.

예시

A B C
D E F
H G -

3x3 칸에 다음과 같이 알파벳이 나열되어있는데 H와 G의 자리를 바꿔서 올바르게 순서대로 정렬할 수 있을까?

규칙은 퍼즐을 빈칸으로 움직이는것 밖에 없고 이는 두 방법으로 구체화된다.

1. 빈 칸의 아래 혹은 위에 있는 퍼즐을 빈 칸으로 옮기는 것 (열 이동)
2. 빈 칸의 왼쪽 혹은 오른쪽에 있는 퍼즐을 빈 칸으로 옮기는 것 (행 이동)

이 두 방법을 어떻게 조합해도 바꿀수 없는 어떤 성질을 찾는다면 뭐가 될 수 있을까?

1. 일단 행 이동은 알파벳 나열 순서를 바꾸지 못한다.

A B C
D E F
H - G

위 처럼 초기 상태에서 G를 옮겨도 나열 순서는 바뀌지 않는다. 오직 열 이동만이 나열 순서를 바꿀 수 있다.

2. 열 이동은 자기 앞이나 뒤에 있는 두 개의 퍼즐들의 상대적 순서를 바꾼다.

A B C
D - F
H E G

위 처럼 E를 한 칸 내리면서 열 이동을 가하면, E 뒤에 있는 F와 H의 위치값(순서)가 1씩 늘어나고 옮겨진 퍼즐 자신은 -2가 된다.

3. 움직이는 동안 역전된 쌍의 개수는 2개씩 변화하거나(열 이동) 혹은 그대로다(행 이동) 역전쌍이란 초기 상태에 G와 H의 순서가 서로 바뀌어있던것 처럼, 원래 순서와 달리 배치되어있는 두 알파벳을 한 쌍으로 묶은것을 칭하기로 한다. 초기 상태에는 G와 H만 빼고 나머지는 순서가 일치했기에 연전쌍은 (G,H) 하나뿐이다. 그런데 위의 2번 열 이동의 예시를 보면 역전쌍의 개수가 2개 늘어나는것을 볼 수가 있다. A>B>C>D>E>F>G>H 가 맞는 순서인데 지금은 A>B>C>D>F>H>E>G 이렇게 나열되어 있다. F보다 앞에 있어야 할 E가 F뒤에 있으니 역전쌍이 생긴다. (E,F) H보다 앞에 있어야 할 E와 G가 H뒤에 있으니 역전쌍이 생긴다. (E,H) (G,H) 역전쌍의 개수는 3개로 초기 1개에서 +2가 됐다. (다시 그대로 E를 위로 올리면 -2로 역전쌍의 개수는 1개가 된다.)

여기서 불변식은 바로 초기에 역전쌍의 개수가 홀수라는 것이고, 어떻게 변화를 조합해도 역전쌍의 개수의 parity(홀짝여부) 는 변하지 않기 때문에 목표상태에 도달할 수 없다.