15퍼즐 또는 16퍼즐

일단 15퍼즐이란 미국의 퍼즐 작가 샘 로이드가 발명한 퍼즐로,

루빅스 큐브처럼 우리에겐 추억의 퍼즐 중 하나지

이 퍼즐이 크게 히트 치면서 당시에 유행하던 루빅스 큐브보다도 중독성이 강했다고 하고,

어떤 회사에서는 업무 중에 이 퍼즐을 가지고 노는 것을 금지 시키기도 했대

다들 알겠지만 마지막 자리에 빈칸이 있고 나머지 칸에 숫자가 적힌 블럭이 있어서,

블럭을 빈칸으로 옮겨 가면서 배열을 바꿨다가 원래 대로 맞추는 퍼즐이야

배열을 바꾸고 원래 대로 맞춘다는 점에서 루빅스 큐브와 비슷한 점이 많지. 큐브의 2차원 판이라고 보면 돼.

샘 로이드는 이 퍼즐을 유행시키기 위한 마케팅의 일환으로 다음과 같은 그림을 주면서 이 문제에 현상금 천 달러를 걸었어

그림을 보면 14와 15가 바뀌어 있지?

이 배열을 빈칸 옮기기를 통해 원래의 배열로 바꿀 수 있느냐가 문제였지

원래 대로 옮기는 사람한테 천 달러를 주겠다고 한 거야

오늘 우리가 다룰 주제는 샘 로이드가 낸 퍼즐의 해결 가능성을 수학적으로 증명하는 거야

여기선 치환이라는 수학 개념을 쓸 건데, 특히 호환이라는 특수한 치환만 다룰 거야

치환이란, 말 그대로 원래의 배열이 주어지면 다른 배열로 바꾸는 것을 말해

수학 연산 중에 하나고 예를 들어 1,2,3,4,5,6,7,8,9,10 을 1,2,5,4,3,6,7,8,9,10 으로 바꾸면 치환이지

모든 치환은 둘 씩 짝지어서 바꾸는 것으로 표현이 가능한데, 여기서 둘 씩 짝지어서 바꾸는 것을 호환이라고 해

즉, 호환은 길이가 2인 치환을 말하는 거지 

위 예시에서 3과 5를 바꿨으니까, 3과 5를 바꾸는 연산을 간단하게 (3 5) 라고 쓰자고 약속한 거야

다시 말하지만 모든 치환은 호환의 연산으로 표현 가능해

예를 들어보면 (1 2 3 4 5) 를 (3 1 5 4 2) 으로 치환했다고 할게

이건 (1 3)(3 5)(2 5) 로 표현돼

즉, (3 1 5 4 2) = (1 3)(3 5)(2 5)

호환의 연산을 간단히 호환의 곱이라 표현해

호환은 교환법칙이 성립하지 않는다는 것에 주의해야 돼

이 글에서는 뒤에 있는 호환부터 차례대로 바꾼다고 약속하고 갈게

다음으로, 치환을 몇 번 했는데 원래 대로 돌아오는 경우를 생각해 볼게

예를 들어 (3 5)(3 5) 는 3과 5를 바꿨다가 다시 바꾸니까 원래 대로 돌아오지?

똑같이 (2 4)(3 5)(2 4)(3 5) 또한 원래대로 돌아오는 연산이 되지

원래 대로 돌아오는 치환을 항등 치환이라고 하고 e로 표기할게

호환에서 중요한 성질은

항등 치환은 무조건 짝수 개의 호환의 곱으로 표시된다는 것이야

증명은 약간 복잡하기 때문에 글 마무리에 <부록>으로 넣을게

궁금한 사람만 보면 될 것 같아

이 성질은 실생활에서도 적용할 수 있는데,

만약 자기 이름이 적힌 명함을 가지고 있는 사람끼리 

한 번에 두 사람씩 서로의 명함을 교환한다고 치고, 몇 번 교환했더니 모든 사람이 다시 자기 명함을 받았다고 치자

그러면 무조건 교환 횟수는 짝수가 되어야 해

홀수 번 교환해서는 항등치환 즉, 원래 대로 돌아오는게 불가능하다는 얘기야 

수학 개념은 여기까지 소개하고 다시 15퍼즐로 돌아오자

15퍼즐을 행렬로 표현해 봤어

0은 빈칸을 의미해

15퍼즐에서 치환이란, 무조건 빈칸을 써야 하니까 여기서는 0과, 0 주변에 붙어있는 숫자의 치환만 가능하겠네

샘 로이드가 낸 문제는 몇 번의 15퍼즐식 치환을 통해 14와 15의 위치만 바꿀 수 있냐는 문제가 돼

15퍼즐식 치환을 수학 개념을 써서 제대로 표현해보자

예시를 써 볼게

그림이 잘 안 보이는데, 상하 치환은 붉은 선으로, 좌우 치환은 파란 선으로 표시했어

즉, 12를 내리고 11을 오른쪽으로 옮기고 15를 위로 올리고 12를 왼쪽으로 옮긴다는 걸 호환으로 표시한거야

15퍼즐에서 모든 호환은 (0, a) 로 표시되는 건 자명하지

이 번엔 더 복잡하게.

상하로 4번 옮기고 좌우로 4번 옮겨봤어

그러면 호환은 8개가 되겠지

눈치 챈 게이들도 있겠지만, 0이 다시 자기 자리로 돌아오려면 짝수 개의 호환으로 표시 되어야 해

당연히 위로 갔으면 아래로 내려와야 하고 왼쪽으로 갔으면 오른쪽으로 가야겠지

즉, 위쪽+왼쪽 = 아래쪽+오른쪽 이니까 전체 치환 위쪽+왼쪽+아래쪽+오른쪽 은 짝수가 되어야 해

따라서 다음과 같은 공식을 얻어

0이 0 자리로 돌아오는 치환은 짝수 개의 호환으로 표시된다

샘 로이드 퍼즐 대로 몇 번의 15퍼즐 치환을 통해서 (14 15) 치환을 만들었다고 가정하자

그러면 어떤 호환들의 곱인지는 모르지만 아무튼 짝수 개의 호환의 곱으로 표시 돼

양변에 (14 15) 호환을 곱해주면

좌변은 홀수 개의 호환의 곱이고

우변은 (14 15)(14 15) 가 되면서 항등 치환이 되네

이 것은 항등 치환이 짝수 개의 호환의 곱으로 표시된다는 사실과 모순이야

즉, 가정이 틀렸다는 것이고, 샘 로이드 그림대로 퍼즐을 옮기는게 애초에 불가능했다는 거지

샘 로이드 저 새끼는 이 사실을 알고 있었어

돈 안 줘도 되니까 천 달러를 건 거겠지

이처럼 퍼즐을 직접 옮겨 보는 헛수고 대신에, 수학적 개념을 써서 쉽게 증명할 수 있어

글은 여기까지고 부록은 그냥 넘기는 걸 추천 ^^

<부록> ===========================================================

증명) 항등 치환은 짝수 개의 호환의 곱으로만 표시된다

일단 항등 치환 e가 n개의 호환의 곱으로 표시된다고 둔다

k번째 호환을 간단히 (호k) 라고 쓰자

맨 끝에 있는 호환 (호n) 에 포함된 원소 m을 정의하고, 그 앞에 있는 호환 (호n-1) 을 4가지 경우로 나눌 수 있다

① (m x) 인 경우 

(m x) (m x) = e 이므로 원래의 항등 치환은 n-2 개의 호환의 곱이 된다

다시 맨 끝에 있는 호환 (호n-2) 에 포함된 원소 m을 정의하면 된다

이렇게 정의하면 m은 없어지지 않는다

② (m y) 인 경우         단, x≠y (이하 문자가 다르면 다른 원소)

(m y)(m x) = (m x)(x y) 가 성립한다

예를 들어 (m x y) 를 둘 다 (x y m) 로 바꾼다

즉, 다음이 성립한다

잘 보면 m은 앞으로 나오고 (m x) 뒤에는 m을 포함하는 호환이 없다

③ (x y) 인 경우

(x y)(m x) = (m y)(x y) 가 성립한다

예를 들어 (m x y) 를 둘 다 (y m x) 로 바꾼다

즉, 다음이 성립한다

2번 경우와 마찬가지로 m이 앞으로 나오고 뒤에 나오는 호환에는 m이 없다

④ (y z) 인 경우

(y z)(m x) = (m x)(y z) 가 성립한다

예를 들어 (y z m x) 를 둘 다 (z y x m) 으로 바꾼다

즉, 다음이 성립한다

역시 m이 앞으로 나오고 뒤에는 m이 없다

1번 경우를 k번 반복할 때 e의 호환은 n-2k 로 줄어든다

e의 호환의 개수 n을 홀수라고 가정하자

n-2k 역시 홀수 개가 된다

2,3,4 모든 경우에 m이 앞으로 나오므로 위와 같은 치환을 마치면

즉, m은 맨 앞에 나오고, 그 뒤에 호환에는 m이 포함된 호환은 없다

m과 짝을 이루는 호환을 c라고 둔다, 물론 m≠c 다 

원래 배열에서 원소 m의 위치를 생각하자

호환을 모두 계산하면, m은 c와 한 번 바뀐다

즉, m이 자기 자리로 돌아오지 않기 때문에 항등치환이 될 수 없다

이는 모순이므로 e는 홀수개의 호환의 곱으로는 표시할 수 없다

따름 정리로, 모든 치환은 짝수 개의 호환의 곱, 아니면 홀수 개의 호환의 곱으로 표시 된다

동시에 짝수 개의 호환의 곱이면서 홀수 개의 호환의 곱으로 표시 되지 않는다

<부록> ===========================================================